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 19bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamathimport com.android.dx.cf.iface.MethodList; 20fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.AccessFlags; 21fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.BasicBlock; 22fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.BasicBlockList; 23fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.Insn; 24fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.InsnList; 25fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.PlainCstInsn; 26fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.PlainInsn; 27fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 28fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 29fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.Rop; 30fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.RopMethod; 31fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.Rops; 32fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.SourcePosition; 33fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.ThrowingCstInsn; 34fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.ThrowingInsn; 35fe107fb6e3f308ac5174ebdc5a794ee880c741d9Jesse Wilsonimport com.android.dx.rop.code.TranslationAdvice; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstInteger; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstType; 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Prototype; 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.StdTypeList; 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Type; 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.TypeList; 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Bits; 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Hex; 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 4538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 4838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Rousselimport java.util.Collection; 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashMap; 5038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Rousselimport java.util.Map; 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Utility that converts a basic block list into a list of register-oriented 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocks. 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class Ropper { 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the parameter assignment block */ 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int PARAM_ASSIGNMENT = -1; 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the return block */ 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int RETURN = -2; 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the synchronized method final return block */ 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_RETURN = -3; 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the first synchronized method setup block */ 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_SETUP_1 = -4; 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the second synchronized method setup block */ 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_SETUP_2 = -5; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label offset for the first synchronized method exception 7439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * handler block 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_CATCH_1 = -6; 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label offset for the second synchronized method exception 8039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * handler block 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_CATCH_2 = -7; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** number of special label offsets */ 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SPECIAL_LABEL_COUNT = 7; 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} method being converted */ 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ConcreteMethod method; 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} original block list */ 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ByteBlockList blocks; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** max locals of the method */ 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int maxLocals; 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** max label (exclusive) of any original bytecode block */ 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int maxLabel; 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} simulation machine to use */ 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final RopperMachine machine; 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 10299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} simulator to use */ 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Simulator sim; 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 10639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code non-null;} sparse array mapping block labels to initial frame 10739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * contents, if known 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Frame[] startFrames; 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 11199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} output block list in-progress */ 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<BasicBlock> result; 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 11599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code non-null;} list of subroutine-nest labels 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (See {@link Frame#getSubroutines} associated with each result block. 11739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Parallel to {@link Ropper#result}. 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<IntList> resultSubroutines; 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 12299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code non-null;} for each block (by label) that is used as an exception 12338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * handler in the input, the exception handling info in Rop. 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 12538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private final CatchInfo[] catchInfos; 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * whether an exception-handler block for a synchronized method was 12939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * ever required 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean synchNeedsExceptionHandler; 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** 13439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code non-null;} list of subroutines indexed by label of start 13539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * address */ 13639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein private final Subroutine[] subroutines; 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** true if {@code subroutines} is non-empty */ 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean hasSubroutines; 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 14138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** Allocates labels of exception handler setup blocks. */ 14238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private final ExceptionSetupLabelAllocator exceptionSetupLabelAllocator; 14338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 14438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 14538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Keeps mapping of an input exception handler target code and how it is generated/targeted in 14638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Rop. 14738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 14838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private class CatchInfo { 14938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 15038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * {@code non-null;} map of ExceptionHandlerSetup by the type they handle */ 15138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private final Map<Type, ExceptionHandlerSetup> setups = 15238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel new HashMap<Type, ExceptionHandlerSetup>(); 15338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 15438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 15538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Get the {@link ExceptionHandlerSetup} corresponding to the given type. The 15638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * ExceptionHandlerSetup is created if this the first request for the given type. 15738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * 15838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @param caughtType {@code non-null;} the type catch by the requested setup 15938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @return {@code non-null;} the handler setup block info for the given type 16038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 16138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel ExceptionHandlerSetup getSetup(Type caughtType) { 16238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel ExceptionHandlerSetup handler = setups.get(caughtType); 16338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel if (handler == null) { 16438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel int handlerSetupLabel = exceptionSetupLabelAllocator.getNextLabel(); 16538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel handler = new ExceptionHandlerSetup(caughtType, handlerSetupLabel); 16638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel setups.put(caughtType, handler); 16738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 16838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return handler; 16938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 17038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 17138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 17238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Get all {@link ExceptionHandlerSetup} of this handler. 17338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * 17438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @return {@code non-null;} 17538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 17638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel Collection<ExceptionHandlerSetup> getSetups() { 17738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return setups.values(); 17838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 17938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 18038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 18138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 18238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Keeps track of an exception handler setup. 18338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 18438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private static class ExceptionHandlerSetup { 18538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 18638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * {@code non-null;} The caught type. */ 18738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private Type caughtType; 18838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 18938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * {@code >= 0;} The label of the exception setup block. */ 19038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private int label; 19138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 19238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 19338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Constructs instance. 19438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * 19538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @param caughtType {@code non-null;} the caught type 19638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @param label {@code >= 0;} the label 19738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 19838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel ExceptionHandlerSetup(Type caughtType, int label) { 19938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel this.caughtType = caughtType; 20038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel this.label = label; 20138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 20238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 20338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 20438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @return {@code non-null;} the caught type 20538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 20638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel Type getCaughtType() { 20738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return caughtType; 20838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 20938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 21038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 21138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @return {@code >= 0;} the label 21238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 21338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel public int getLabel() { 21438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return label; 21538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 21638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 21738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Keeps track of subroutines that exist in java form and are inlined in 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Rop form. 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private class Subroutine { 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of all blocks that jsr to this subroutine */ 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet callerBlocks; 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** List of all blocks that return from this subroutine */ 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet retBlocks; 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** first block in this subroutine */ 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int startBlock; 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startBlock First block of the subroutine. 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine(int startBlock) { 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.startBlock = startBlock; 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project retBlocks = new BitSet(maxLabel); 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project callerBlocks = new BitSet(maxLabel); 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hasSubroutines = true; 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startBlock First block of the subroutine. 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param retBlock one of the ret blocks (final blocks) of this 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine. 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine(int startBlock, int retBlock) { 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this(startBlock); 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addRetBlock(retBlock); 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 25599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the label of the subroutine's start block. 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int getStartBlock() { 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startBlock; 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a label to the list of ret blocks (final blocks) for this 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine. 26439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param retBlock ret block label 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void addRetBlock(int retBlock) { 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project retBlocks.set(retBlock); 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a label to the list of caller blocks for this subroutine. 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label a block that invokes this subroutine. 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void addCallerBlock(int label) { 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project callerBlocks.set(label); 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Generates a list of subroutine successors. Note: successor blocks 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * could be listed more than once. This is ok, because this successor 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * list (and the block it's associated with) will be copied and inlined 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * before we leave the ropper. Redundent successors will result in 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * redundent (no-op) merges. 28639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return all currently known successors 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (return destinations) for that subroutine 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList getSuccessors() { 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = new IntList(callerBlocks.size()); 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 29441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein * For each subroutine caller, get it's target. If the 29541aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein * target is us, add the ret target (subroutine successor) 29641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein * to our list 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 29941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int label = callerBlocks.nextSetBit(0); label >= 0; 30041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein label = callerBlocks.nextSetBit(label+1)) { 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock subCaller = labelToBlock(label); 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.add(subCaller.getSuccessors().get(0)); 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.setImmutable(); 30639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return successors; 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merges the specified frame into this subroutine's successors, 31299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * setting {@code workSet} as appropriate. To be called with 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the frame of a subroutine ret block. 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 31599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param frame {@code non-null;} frame from ret block to merge 31699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param workSet {@code non-null;} workset to update 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void mergeToSuccessors(Frame frame, int[] workSet) { 31941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int label = callerBlocks.nextSetBit(0); label >= 0; 32041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein label = callerBlocks.nextSetBit(label+1)) { 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock subCaller = labelToBlock(label); 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succLabel = subCaller.getSuccessors().get(0); 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame subFrame = frame.subFrameForLabel(startBlock, label); 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subFrame != null) { 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mergeAndWorkAsNecessary(succLabel, -1, null, 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subFrame, workSet); 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, label); 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Converts a {@link ConcreteMethod} to a {@link RopMethod}. 33839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 33999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param method {@code non-null;} method to convert 34099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param advice {@code non-null;} translation advice to use 341bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath * @param methods {@code non-null;} list of methods defined by the class 342bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath * that defines {@code method}. 34399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the converted instance 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static RopMethod convert(ConcreteMethod method, 346bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath TranslationAdvice advice, MethodList methods) { 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 348bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath Ropper r = new Ropper(method, advice, methods); 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project r.doit(); 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return r.getRopMethod(); 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while working on method " + 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project method.getNat().toHuman()); 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. This class is not publicly instantiable; use 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #convert}. 36139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 36299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param method {@code non-null;} method to convert 36399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param advice {@code non-null;} translation advice to use 364bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath * @param methods {@code non-null;} list of methods defined by the class 365bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath * that defines {@code method}. 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 367bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath private Ropper(ConcreteMethod method, TranslationAdvice advice, MethodList methods) { 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (method == null) { 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("method == null"); 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (advice == null) { 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("advice == null"); 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.method = method; 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.blocks = BasicBlocker.identifyBlocks(method); 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.maxLabel = blocks.getMaxLabel(); 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.maxLocals = method.getMaxLocals(); 380bb17e210dd396f0bfa6e209b4cae9828a045e291Narayan Kamath this.machine = new RopperMachine(this, method, advice, methods); 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.sim = new Simulator(machine, method); 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.startFrames = new Frame[maxLabel]; 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.subroutines = new Subroutine[maxLabel]; 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The "* 2 + 10" below is to conservatively believe that every 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block is an exception handler target and should also 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * take care of enough other possible extra overhead such that 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the underlying array is unlikely to need resizing. 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.result = new ArrayList<BasicBlock>(blocks.size() * 2 + 10); 39239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein this.resultSubroutines = 39339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein new ArrayList<IntList>(blocks.size() * 2 + 10); 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 39538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel this.catchInfos = new CatchInfo[maxLabel]; 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.synchNeedsExceptionHandler = false; 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Set up the first stack frame with the right limits, but leave it 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * empty here (to be filled in outside of the constructor). 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[0] = new Frame(maxLocals, method.getMaxStack()); 40338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel exceptionSetupLabelAllocator = new ExceptionSetupLabelAllocator(); 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the first (lowest) register number to use as the temporary 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * area when unwinding stack manipulation ops. 40939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 41099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the first register to use 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /*package*/ int getFirstTempStackReg() { 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We use the register that is just past the deepest possible 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * stack element, plus one if the method is synchronized to 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * avoid overlapping with the synch register. We don't need to 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * do anything else special at this level, since later passes 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * will merely notice the highest register used by explicit 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * inspection. 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int regCount = getNormalRegCount(); 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return isSynchronized() ? regCount + 1 : regCount; 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the label for the given special-purpose block. The given label 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * should be one of the static constants defined by this class. 42839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 42999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code < 0;} the special label constant 43099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the actual label value to use 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getSpecialLabel(int label) { 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The label is bitwise-complemented so that mistakes where 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * LABEL is used instead of getSpecialLabel(LABEL) cause a 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * failure at block construction time, since negative labels 43738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * are illegal. 0..maxLabel (exclusive) are the original blocks and 43838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * maxLabel..(maxLabel + method.getCatches().size()) are reserved for exception handler 43938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * setup blocks (see getAvailableLabel(), exceptionSetupLabelAllocator). 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 44138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return maxLabel + method.getCatches().size() + ~label; 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the minimum label for unreserved use. 44639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 44799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the minimum label 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getMinimumUnreservedLabel() { 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 45138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * The labels below (maxLabel + method.getCatches().size() + SPECIAL_LABEL_COUNT) are 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * reserved for particular uses. 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 45538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return maxLabel + method.getCatches().size() + SPECIAL_LABEL_COUNT; 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 45938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Gets an unreserved and available label. 46038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Labels are distributed this way: 46138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * <ul> 46238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * <li>[0, maxLabel[ are the labels of the blocks directly 46338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * corresponding to the input bytecode.</li> 46438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * <li>[maxLabel, maxLabel + method.getCatches().size()[ are reserved for exception setup 46538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * blocks.</li> 46638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * <li>[maxLabel + method.getCatches().size(), 46738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * maxLabel + method.getCatches().size() + SPECIAL_LABEL_COUNT[ are reserved for special blocks, 46838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * ie param assignement, return and synch blocks.</li> 46938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * <li>[maxLabel method.getCatches().size() + SPECIAL_LABEL_COUNT, getAvailableLabel()[ assigned 47038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * labels. Note that some 47138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * of the assigned labels may not be used any more if they were assigned to a block that was 47238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * deleted since.</li> 47338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * </ul> 47439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 47538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * @return {@code >= 0;} an available label with the guaranty that all greater labels are 47638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * also available. 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getAvailableLabel() { 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int candidate = getMinimumUnreservedLabel(); 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (BasicBlock bb : result) { 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = bb.getLabel(); 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label >= candidate) { 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project candidate = label + 1; 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return candidate; 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets whether the method being translated is synchronized. 49339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether the method being translated is synchronized 495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isSynchronized() { 497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int accessFlags = method.getAccessFlags(); 498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0; 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets whether the method being translated is static. 50339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether the method being translated is static 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isStatic() { 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int accessFlags = method.getAccessFlags(); 508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (accessFlags & AccessFlags.ACC_STATIC) != 0; 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the total number of registers used for "normal" purposes (i.e., 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for the straightforward translation from the original Java). 51439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 51599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the total number of registers used 516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getNormalRegCount() { 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return maxLocals + method.getMaxStack(); 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the register spec to use to hold the object to synchronize on, 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for a synchronized method. 52439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 52599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the register spec 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private RegisterSpec getSynchReg() { 528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We use the register that is just past the deepest possible 530c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein * stack element, with a minimum of v1 since v0 is what's 531c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein * always used to hold the caught exception when unwinding. We 532c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein * don't need to do anything else special at this level, since 533c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein * later passes will merely notice the highest register used 534c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein * by explicit inspection. 535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 536c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein int reg = getNormalRegCount(); 537c51439a513d4cc3c2be4a7cce7b3e9ae480fd5c2Dan Bornstein return RegisterSpec.make((reg < 1) ? 1 : reg, Type.OBJECT); 538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 54139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Searches {@link #result} for a block with the given label. Returns its 54239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * index if found, or returns {@code -1} if there is no such block. 54339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label the label to look for 54599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= -1;} the index for the block with the given label or 54699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code -1} if there is no such block 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int labelToResultIndex(int label) { 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = result.size(); 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = result.get(i); 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one.getLabel() == label) { 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return i; 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 55839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein } 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 56139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Searches {@link #result} for a block with the given label. Returns it if 56239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * found, or throws an exception if there is no such block. 56339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label the label to look for 56599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the block with the given label 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BasicBlock labelToBlock(int label) { 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(label); 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("no such label " + 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Hex.u2(label)); 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result.get(idx); 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a block to the output result. 58039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 58199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block to add 58239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutines {@code non-null;} subroutine label list 58339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * as described in {@link Frame#getSubroutines} 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addBlock(BasicBlock block, IntList subroutines) { 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block == null) { 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("block == null"); 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(block); 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(subroutines); 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds or replace a block in the output result. If this is a 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * replacement, then any extra blocks that got added with the 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * original get removed as a result of calling this method. 59939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 60099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block to add or replace 60139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutines {@code non-null;} subroutine label list 60239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * as described in {@link Frame#getSubroutines} 60399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} if the block was replaced or 60499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code false} if it was added for the first time 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean addOrReplaceBlock(BasicBlock block, IntList subroutines) { 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block == null) { 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("block == null"); 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(block.getLabel()); 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean ret; 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = false; 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We are replacing a pre-existing block, so find any 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocks that got added as part of the original and 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * remove those too. Such blocks are (possibly indirect) 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successors of this block which are out of the range of 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * normally-translated blocks. 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeBlockAndSpecialSuccessors(idx); 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = true; 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(block); 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(subroutines); 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds or replaces a block in the output result. Do not delete 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * any successors. 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 63899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block to add or replace 63939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutines {@code non-null;} subroutine label list 64039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * as described in {@link Frame#getSubroutines} 64199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} if the block was replaced or 64299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code false} if it was added for the first time 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean addOrReplaceBlockNoDelete(BasicBlock block, 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList subroutines) { 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block == null) { 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("block == null"); 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(block.getLabel()); 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean ret; 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = false; 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.remove(idx); 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.remove(idx); 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = true; 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(block); 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(subroutines); 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #addOrReplaceBlock} which recursively removes 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the given block and all blocks that are (direct and indirect) 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successors of it whose labels indicate that they are not in the 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * normally-translated range. 67239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 67399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param idx {@code non-null;} block to remove (etc.) 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void removeBlockAndSpecialSuccessors(int idx) { 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int minLabel = getMinimumUnreservedLabel(); 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock block = result.get(idx); 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = block.getSuccessors(); 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = successors.size(); 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.remove(idx); 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.remove(idx); 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = successors.get(i); 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label >= minLabel) { 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project idx = labelToResultIndex(label); 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("Invalid label " 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + Hex.u2(label)); 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeBlockAndSpecialSuccessors(idx); 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Extracts the resulting {@link RopMethod} from the instance. 69939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 70099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the method object 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private RopMethod getRopMethod() { 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Construct the final list of blocks. 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = result.size(); 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlockList bbl = new BasicBlockList(sz); 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bbl.set(i, result.get(i)); 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bbl.setImmutable(); 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Construct the method object to wrap it all up. 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Note: The parameter assignment block is always the first 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * that should be executed, hence the second argument to the 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constructor. 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT)); 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does the conversion. 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void doit() { 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] workSet = Bits.makeBitSet(maxLabel); 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, 0); 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addSetupBlocks(); 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setFirstFrame(); 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int offset = Bits.findFirst(workSet, 0); 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (offset < 0) { 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.clear(workSet, offset); 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ByteBlock block = blocks.labelToBlock(offset); 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame frame = startFrames[offset]; 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processBlock(block, frame, workSet); 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while working on block " + Hex.u2(offset)); 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addReturnBlock(); 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addSynchExceptionHandlerBlock(); 751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addExceptionSetupBlocks(); 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasSubroutines) { 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Subroutines are very rare, so skip this step if it's n/a 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project inlineSubroutines(); 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets up the first frame to contain all the incoming parameters in 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * locals. 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void setFirstFrame() { 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Prototype desc = method.getEffectiveDescriptor(); 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[0].initializeWithParameters(desc.getParameterTypes()); 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[0].setImmutable(); 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Processes the given block. 77139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 77299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} block to process 77399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param frame {@code non-null;} start frame for the block 77439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param workSet {@code non-null;} bits representing work to do, 77539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * which this method may add to 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processBlock(ByteBlock block, Frame frame, int[] workSet) { 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Prepare the list of caught exceptions for this block. 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ByteCatchList catches = block.getCatches(); 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project machine.startBlock(catches.toRopCatchList()); 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Using a copy of the given frame, simulate each instruction, 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * calling into machine for each. 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project frame = frame.copy(); 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sim.simulate(block, frame); 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project frame.setImmutable(); 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int extraBlockCount = machine.getExtraBlockCount(); 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<Insn> insns = machine.getInsns(); 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int insnSz = insns.size(); 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merge the frame into each possible non-exceptional 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successor. 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int catchSz = catches.size(); 800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = block.getSuccessors(); 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int startSuccessorIndex; 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine calledSubroutine = null; 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (machine.hasJsr()) { 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If this frame ends in a JSR, only merge our frame with 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine start, not the subroutine's return target. 809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = 1; 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int subroutineLabel = successors.get(1); 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines[subroutineLabel] == null) { 81539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein subroutines[subroutineLabel] = 81639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein new Subroutine (subroutineLabel); 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 81839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel].addCallerBlock(block.getLabel()); 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calledSubroutine = subroutines[subroutineLabel]; 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (machine.hasRet()) { 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This block ends in a ret, which means it's the final block 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in some subroutine. Ultimately, this block will be copied 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and inlined for each call and then disposed of. 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ReturnAddress ra = machine.getReturnAddress(); 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int subroutineLabel = ra.getSubroutineAddress(); 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines[subroutineLabel] == null) { 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel] 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new Subroutine (subroutineLabel, block.getLabel()); 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel].addRetBlock(block.getLabel()); 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = subroutines[subroutineLabel].getSuccessors(); 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel] 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .mergeToSuccessors(frame, workSet); 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Skip processing below since we just did it. 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = successors.size(); 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (machine.wereCatchesUsed()) { 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If there are catches, then the first successors 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (which will either be all of them or all but the last one) 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are catch targets. 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 850f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = catchSz; 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 852f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = 0; 853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 854f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 855f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succSz = successors.size(); 856f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = startSuccessorIndex; i < succSz; 857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++) { 858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succ = successors.get(i); 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mergeAndWorkAsNecessary(succ, block.getLabel(), 861f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calledSubroutine, frame, workSet); 862f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while merging to block " + Hex.u2(succ)); 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((succSz == 0) && machine.returns()) { 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The block originally contained a return, but it has 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * been made to instead end with a goto, and we need to 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * tell it at this point that its sole successor is the 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * return block. This has to happen after the merge loop 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * above, since, at this point, the return block doesn't 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * actually exist; it gets synthesized at the end of 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * processing the original blocks. 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 878f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = IntList.makeImmutable(getSpecialLabel(RETURN)); 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succSz = 1; 880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySucc; 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succSz == 0) { 885f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = -1; 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = machine.getPrimarySuccessorIndex(); 888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySucc >= 0) { 889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = successors.get(primarySucc); 890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This variable is true only when the method is synchronized and 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the block being processed can possibly throw an exception. 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean synch = isSynchronized() && machine.canThrow(); 898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (synch || (catchSz != 0)) { 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Deal with exception handlers: Merge an exception-catch 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * frame into each possible exception handler, and 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * construct a new set of successors to point at the 904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * exception handler setup blocks (which get synthesized 905f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * at the very end of processing). 906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean catchesAny = false; 908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newSucc = new IntList(succSz); 909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < catchSz; i++) { 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ByteCatchList.Item one = catches.get(i); 911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstType exceptionClass = one.getExceptionClass(); 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int targ = one.getHandlerPc(); 913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project catchesAny |= (exceptionClass == CstType.OBJECT); 915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass); 917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 918f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mergeAndWorkAsNecessary(targ, block.getLabel(), 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project null, f, workSet); 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while merging exception to block " + 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Hex.u2(targ)); 924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 92838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Set up the exception handler type. 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 93038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel CatchInfo handlers = catchInfos[targ]; 93138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel if (handlers == null) { 93238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel handlers = new CatchInfo(); 93338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel catchInfos[targ] = handlers; 934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 93538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel ExceptionHandlerSetup handler = handlers.getSetup(exceptionClass.getClassType()); 936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 937f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 93838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * The synthesized exception setup block will have the label given by handler. 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 94038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel newSucc.add(handler.getLabel()); 941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (synch && !catchesAny) { 944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The method is synchronized and this block doesn't 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * already have a catch-all handler, so add one to the 947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * end, both in the successors and in the throwing 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction(s) at the end of the block (which is where 949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the caught classes live). 950f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.add(getSpecialLabel(SYNCH_CATCH_1)); 952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project synchNeedsExceptionHandler = true; 953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 954f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) { 955f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = insns.get(i); 956f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.canThrow()) { 957f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = insn.withAddedCatch(Type.OBJECT); 958f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, insn); 959f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 960f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 961f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 962f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySucc >= 0) { 964f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.add(primarySucc); 965f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 967f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.setImmutable(); 968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = newSucc; 969f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Construct the final resulting block(s), and store it (them). 972f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccListIndex = successors.indexOf(primarySucc); 974f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 975f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 976f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If there are any extra blocks, work backwards through the 977f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * list of instructions, adding single-instruction blocks, and 978f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * resetting the successors variables as appropriate. 979f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 980f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (/*extraBlockCount*/; extraBlockCount > 0; extraBlockCount--) { 981f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 982f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Some of the blocks that the RopperMachine wants added 983f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are for move-result insns, and these need goto insns as well. 984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 985f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn extraInsn = insns.get(--insnSz); 986f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean needsGoto 987f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = extraInsn.getOpcode().getBranchingness() 988f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project == Rop.BRANCH_NONE; 989f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList il = new InsnList(needsGoto ? 2 : 1); 990f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList extraBlockSuccessors = successors; 991f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 992f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(0, extraInsn); 993f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 994f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (needsGoto) { 995f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(1, new PlainInsn(Rops.GOTO, 996f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project extraInsn.getPosition(), null, 997f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 998f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 999f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Obviously, this block won't be throwing an exception 1000f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * so it should only have one successor. 1001f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1002f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project extraBlockSuccessors = IntList.makeImmutable(primarySucc); 1003f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1004f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.setImmutable(); 1005f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1006f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = getAvailableLabel(); 1007f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors, 1008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc); 1009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // All of these extra blocks will be in the same subroutine 1010f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, frame.getSubroutines()); 1011f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1012f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = successors.mutableCopy(); 1013f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.set(primarySuccListIndex, label); 1014f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.setImmutable(); 1015f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = label; 1016f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 101739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 1018f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1); 1019f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1020f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1021f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Add a goto to the end of the block if it doesn't already 1022f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * end with a branch, to maintain the invariant that all 1023f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocks end with a branch of some sort or other. Note that 1024f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it is possible for there to be blocks for which no 1025f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instructions were ever output (e.g., only consist of pop* 1026f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the original Java bytecode). 1027f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1028f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((lastInsn == null) || 1029f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) { 1030f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO : 1031f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastInsn.getPosition(); 1032f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(new PlainInsn(Rops.GOTO, pos, null, 1033f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 1034f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insnSz++; 1035f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 103639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 1037f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1038f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Construct a block for the remaining instructions (which in 1039f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the usual case is all of them). 1040f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1041f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1042f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList il = new InsnList(insnSz); 1043f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < insnSz; i++) { 1044f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(i, insns.get(i)); 1045f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1046f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.setImmutable(); 1047f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1048f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = 1049f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(block.getLabel(), il, successors, primarySucc); 1050f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addOrReplaceBlock(bb, frame.getSubroutines()); 1051f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1052f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1053f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1054f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #processBlock}, which merges frames and 1055f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * adds to the work set, as necessary. 105639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 105799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} label to work on 105899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param pred predecessor label; must be {@code >= 0} when 105999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code label} is a subroutine start block and calledSubroutine 1060f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is non-null. Otherwise, may be -1. 106199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param calledSubroutine {@code null-ok;} a Subroutine instance if 106299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code label} is the first block in a subroutine. 106399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param frame {@code non-null;} new frame for the labelled block 106439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param workSet {@code non-null;} bits representing work to do, 106539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * which this method may add to 1066f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1067f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void mergeAndWorkAsNecessary(int label, int pred, 1068f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine calledSubroutine, Frame frame, int[] workSet) { 1069f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame existing = startFrames[label]; 1070f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame merged; 1071f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1072f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (existing != null) { 1073f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1074f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Some other block also continues at this label. Merge 1075f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the frames, and re-set the bit in the work set if there 1076f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * was a change. 1077f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1078f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (calledSubroutine != null) { 1079f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project merged = existing.mergeWithSubroutineCaller(frame, 1080f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calledSubroutine.getStartBlock(), pred); 1081f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1082f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project merged = existing.mergeWith(frame); 1083f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1084f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (merged != existing) { 1085f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[label] = merged; 1086f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, label); 1087f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1088f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1089f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This is the first time this label has been encountered. 1090f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (calledSubroutine != null) { 1091f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[label] 1092f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = frame.makeNewSubroutineStartFrame(label, pred); 1093f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1094f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[label] = frame; 1095f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1096f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, label); 1097f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1098f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1099f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs and adds the blocks that perform setup for the rest of 1102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the method. This includes a first block which merely contains 1103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * assignments from parameters to the same-numbered registers and 1104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a possible second block which deals with synchronization. 1105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addSetupBlocks() { 1107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalVariableList localVariables = method.getLocalVariables(); 1108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = method.makeSourcePosistion(0); 1109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Prototype desc = method.getEffectiveDescriptor(); 1110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList params = desc.getParameterTypes(); 1111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = params.size(); 1112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(sz + 1); 1113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int at = 0; 1114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 1116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type one = params.get(i); 111739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein LocalVariableList.Item local = 111839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein localVariables.pcAndIndexToLocal(0, at); 1119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = (local == null) ? 1120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec.make(at, one) : 1121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec.makeLocalOptional(at, one, local.getLocalItem()); 1122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result, 1124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, 1125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInteger.make(at)); 1126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, insn); 1127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project at += one.getCategory(); 1128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 113039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein insns.set(sz, new PlainInsn(Rops.GOTO, pos, null, 1131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 1132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean synch = isSynchronized(); 1135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0; 1136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = 1137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT), insns, 1138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(label), label); 1139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (synch) { 1142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec synchReg = getSynchReg(); 1143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn; 1144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isStatic()) { 1145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos, 1146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, 1147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY, 1148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project method.getDefiningClass()); 1149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(1); 1150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(2); 1153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos, 1154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project synchReg, RegisterSpecList.EMPTY, 1155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInteger.VALUE_0); 1156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(1, new PlainInsn(Rops.GOTO, pos, null, 1158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 1159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label2 = getSpecialLabel(SYNCH_SETUP_2); 1162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(label, insns, 1164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(label2), label2); 1165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(isStatic() ? 2 : 1); 1168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isStatic()) { 1170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg), 1171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pos, synchReg, RegisterSpecList.EMPTY)); 1172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos, 1175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(synchReg), 1176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(isStatic() ? 1 :0, insn); 1178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0); 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 /** 1185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs and adds the return block, if necessary. The return 118699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * block merely contains an appropriate {@code return} 1187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction. 1188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addReturnBlock() { 1190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop returnOp = machine.getReturnOp(); 1191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (returnOp == null) { 1193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The method being converted never returns normally, so there's 1195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * no need for a return block. 1196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 1198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition returnPos = machine.getReturnPosition(); 1201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = getSpecialLabel(RETURN); 1202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSynchronized()) { 1204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(1); 1205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos, 1206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(getSynchReg()), 1207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextLabel = getSpecialLabel(SYNCH_RETURN); 1212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = 1213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(label, insns, 1214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(nextLabel), nextLabel); 1215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project label = nextLabel; 1218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(1); 1221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypeList sourceTypes = returnOp.getSources(); 1222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources; 1223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (sourceTypes.size() == 0) { 1225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sources = RegisterSpecList.EMPTY; 1226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0)); 1228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sources = RegisterSpecList.make(source); 1229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new PlainInsn(returnOp, returnPos, null, sources); 1232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1); 1236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs and adds, if necessary, the catch-all exception handler 1241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block to deal with unwinding the lock taken on entry to a synchronized 1242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method. 1243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addSynchExceptionHandlerBlock() { 1245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!synchNeedsExceptionHandler) { 1246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The method being converted either isn't synchronized or 1248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can't possibly throw exceptions in its main body, so 1249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * there's no need for a synchronized method exception 1250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * handler. 1251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 1253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = method.makeSourcePosistion(0); 1256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE); 1257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb; 1258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn; 1259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(2); 1261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos, 1262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exReg, RegisterSpecList.EMPTY); 1263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos, 1265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(getSynchReg()), 1266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(1, insn); 1268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label2 = getSpecialLabel(SYNCH_CATCH_2); 1271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns, 1272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(label2), label2); 1273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(1); 1276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingInsn(Rops.THROW, pos, 1277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(exReg), 1278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(label2, insns, IntList.EMPTY, -1); 1283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Creates the exception handler setup blocks. "maxLocals" 1288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * below is because that's the register number corresponding 1289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the sole element on a one-deep stack (which is the 1290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * situation at the start of an exception handler block). 1291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addExceptionSetupBlocks() { 1293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel int len = catchInfos.length; 1295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < len; i++) { 129638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel CatchInfo catches = catchInfos[i]; 129738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel if (catches != null) { 129838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel for (ExceptionHandlerSetup one : catches.getSetups()) { 129938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel Insn proto = labelToBlock(i).getFirstInsn(); 130038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel SourcePosition pos = proto.getPosition(); 130138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel InsnList il = new InsnList(2); 130238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 130338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel Insn insn = new PlainInsn(Rops.opMoveException(one.getCaughtType()), 130438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel pos, 130538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel RegisterSpec.make(maxLocals, one.getCaughtType()), 130638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel RegisterSpecList.EMPTY); 130738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel il.set(0, insn); 130838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 130938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel insn = new PlainInsn(Rops.GOTO, pos, null, 131038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel RegisterSpecList.EMPTY); 131138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel il.set(1, insn); 131238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel il.setImmutable(); 131338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 131438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel BasicBlock bb = new BasicBlock(one.getLabel(), 131538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel il, 131638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel IntList.makeImmutable(i), 131738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel i); 131838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel addBlock(bb, startFrames[i].getSubroutines()); 131938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 1320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if the basic block is a subroutine caller block. 1326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 132799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param bb {@code non-null;} the basic block in question 1328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if this block calls a subroutine 1329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isSubroutineCaller(BasicBlock bb) { 1331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = bb.getSuccessors(); 1332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (successors.size() < 2) return false; 1333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int subLabel = successors.get(1); 1335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (subLabel < subroutines.length) 1337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (subroutines[subLabel] != null); 1338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 134139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Inlines any subroutine calls. 1342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void inlineSubroutines() { 1344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final IntList reachableSubroutineCallerLabels = new IntList(4); 1345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Compile a list of all subroutine calls reachable 1348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * through the normal (non-subroutine) flow. We do this first, since 1349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * we'll be affecting the call flow as we go. 135039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Start at label 0 -- the param assignment block has nothing for us 1352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() { 1354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitBlock(BasicBlock b) { 1355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(b)) { 1356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reachableSubroutineCallerLabels.add(b.getLabel()); 1357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 1360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Convert the resultSubroutines list, indexed by block index, 1363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to a label-to-subroutines mapping used by the inliner. 1364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int largestAllocedLabel = getAvailableLabel(); 1366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<IntList> labelToSubroutines 1367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new ArrayList<IntList>(largestAllocedLabel); 1368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < largestAllocedLabel; i++) { 1369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.add(null); 1370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < result.size(); i++) { 1373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock b = result.get(i); 1374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (b == null) { 1375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 1376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList subroutineList = resultSubroutines.get(i); 1378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.set(b.getLabel(), subroutineList); 1379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 138239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Inline all reachable subroutines. 138339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Inner subroutines will be inlined as they are encountered. 138439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein */ 1385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = reachableSubroutineCallerLabels.size(); 1386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0 ; i < sz ; i++) { 1387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = reachableSubroutineCallerLabels.get(i); 1388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new SubroutineInliner( 138939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein new LabelAllocator(getAvailableLabel()), 139039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein labelToSubroutines) 1391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .inlineSubroutineCalledFrom(labelToBlock(label)); 1392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Now find the blocks that aren't reachable and remove them 1395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project deleteUnreachableBlocks(); 1396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Deletes all blocks that cannot be reached. This is run to delete 1400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * original subroutine blocks after subroutine inlining. 1401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void deleteUnreachableBlocks() { 1403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final IntList reachableLabels = new IntList(result.size()); 1404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // subroutine inlining is done now and we won't update this list here 1406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.clear(); 1407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT), 1409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock.Visitor() { 1410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitBlock(BasicBlock b) { 1412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reachableLabels.add(b.getLabel()); 1413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 1415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reachableLabels.sort(); 1417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = result.size() - 1 ; i >= 0 ; i--) { 1419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) { 1420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.remove(i); 1421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // unnecessary here really, since subroutine inlining is done 1422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //resultSubroutines.remove(i); 1423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocates labels, without requiring previously allocated labels 1429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to have been added to the blocks list. 1430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static class LabelAllocator { 1432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextAvailableLabel; 1433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startLabel available label to start allocating from 1436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LabelAllocator(int startLabel) { 1438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nextAvailableLabel = startLabel; 1439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return next available label 1443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int getNextLabel() { 1445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return nextAvailableLabel++; 1446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 145038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel * Allocates labels for exception setup blocks. 145138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel */ 145238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel private class ExceptionSetupLabelAllocator extends LabelAllocator { 145338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel int maxSetupLabel; 145438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 145538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel ExceptionSetupLabelAllocator() { 145638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel super(maxLabel); 145738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel maxSetupLabel = maxLabel + method.getCatches().size(); 145838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 145938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 146038f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel @Override 146138f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel int getNextLabel() { 146238f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel if (nextAvailableLabel >= maxSetupLabel) { 146338f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel throw new IndexOutOfBoundsException(); 146438f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 146538f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel return nextAvailableLabel ++; 146638f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 146738f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel } 146838f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel 146938f3f7c42f4d71e80f98e6bb7b45072fe6b884faYohann Roussel /** 1470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inlines a subroutine. Start by calling 147139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@link #inlineSubroutineCalledFrom}. 1472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private class SubroutineInliner { 1474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 147539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * maps original label to the label that will be used by the 147639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * inlined version 1477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final HashMap<Integer, Integer> origLabelToCopiedLabel; 1479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 148039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** set of original labels that need to be copied */ 1481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet workList; 1482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 148339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** the label of the original start block for this subroutine */ 1484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int subroutineStart; 1485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 148639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** the label of the ultimate return block */ 1487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int subroutineSuccessor; 1488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 148939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** used for generating new labels for copied blocks */ 1490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final LabelAllocator labelAllocator; 1491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A mapping, indexed by label, to subroutine nesting list. 1494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The subroutine nest list is as returned by 1495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link Frame#getSubroutines}. 1496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<IntList> labelToSubroutines; 1498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SubroutineInliner(final LabelAllocator labelAllocator, 1500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<IntList> labelToSubroutines) { 1501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project origLabelToCopiedLabel = new HashMap<Integer, Integer>(); 1502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workList = new BitSet(maxLabel); 1504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.labelAllocator = labelAllocator; 1506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.labelToSubroutines = labelToSubroutines; 1507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inlines a subroutine. 151139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 151239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param b block where {@code jsr} occurred in the original bytecode 1513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void inlineSubroutineCalledFrom(final BasicBlock b) { 1515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The 0th successor of a subroutine caller block is where 1517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine should return to. The 1st successor is 1518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the start block of the subroutine. 1519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutineSuccessor = b.getSuccessors().get(0); 1521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutineStart = b.getSuccessors().get(1); 1522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This allocates an initial label and adds the first 1525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block to the worklist. 1526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSubStartLabel = mapOrAllocateLabel(subroutineStart); 1528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 152941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int label = workList.nextSetBit(0); label >= 0; 153041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein label = workList.nextSetBit(0)) { 1531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workList.clear(label); 1532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newLabel = origLabelToCopiedLabel.get(label); 1533f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project copyBlock(label, newLabel); 1535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(labelToBlock(label))) { 1537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new SubroutineInliner(labelAllocator, labelToSubroutines) 1538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .inlineSubroutineCalledFrom(labelToBlock(newLabel)); 1539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replace the original caller block, since we now have a 1544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * new successor 1545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addOrReplaceBlockNoDelete( 1548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(b.getLabel(), b.getInsns(), 1549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable (newSubStartLabel), 155041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein newSubStartLabel), 155141aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein labelToSubroutines.get(b.getLabel())); 15526b386bfb92ef6efe8f963270fc5a4b756fca225ejeffhao } 1553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copies a basic block, mapping its successors along the way. 155639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param origLabel original block label 1558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newLabel label that the new block should have 1559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 15606b386bfb92ef6efe8f963270fc5a4b756fca225ejeffhao private void copyBlock(int origLabel, int newLabel) { 1561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock origBlock = labelToBlock(origLabel); 1563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final IntList origSuccessors = origBlock.getSuccessors(); 1565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors; 1566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccessor = -1; 1567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine subroutine; 1568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(origBlock)) { 1570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A subroutine call inside a subroutine call. 1572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Set up so we can recurse. The caller block should have 1573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it's first successor be a copied block that will be 1574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine's return point. It's second successor will 1575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be copied when we recurse, and remains as the original 1576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label of the start of the inner subroutine. 1577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = IntList.makeImmutable( 1580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapOrAllocateLabel(origSuccessors.get(0)), 1581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project origSuccessors.get(1)); 1582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // primary successor will be set when this block is replaced 1583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (null 1584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project != (subroutine = subroutineFromRetBlock(origLabel))) { 1585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this is a ret block -- its successor 1587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * should be subroutineSuccessor 1588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Sanity check 1591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutine.startBlock != subroutineStart) { 1592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException ( 1593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "ret instruction returns to label " 1594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + Hex.u2 (subroutine.startBlock) 1595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + " expected: " + Hex.u2(subroutineStart)); 1596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = IntList.makeImmutable(subroutineSuccessor); 1599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = subroutineSuccessor; 1600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Map all the successor labels 1602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origPrimary = origBlock.getPrimarySuccessor(); 1604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = origSuccessors.size(); 1605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = new IntList(sz); 1607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0 ; i < sz ; i++) { 1609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origSuccLabel = origSuccessors.get(i); 1610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSuccLabel = mapOrAllocateLabel(origSuccLabel); 1611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.add(newSuccLabel); 1613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (origPrimary == origSuccLabel) { 1615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = newSuccLabel; 1616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.setImmutable(); 1620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock ( 1623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(newLabel, 1624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project filterMoveReturnAddressInsns(origBlock.getInsns()), 1625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors, primarySuccessor), 1626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.get(newLabel)); 1627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if a specified label is involved in a specified 1631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine. 1632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 163399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} a basic block label 163439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutineStart {@code >= 0;} a subroutine as identified 163539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * by the label of its start block 163639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @return true if the block is dominated by the subroutine call 1637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean involvedInSubroutine(int label, int subroutineStart) { 1639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList subroutinesList = labelToSubroutines.get(label); 16406b386bfb92ef6efe8f963270fc5a4b756fca225ejeffhao return (subroutinesList != null && subroutinesList.size() > 0 1641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && subroutinesList.top() == subroutineStart); 1642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps the label of a pre-copied block to the label of the inlined 1646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block, allocating a new label and adding it to the worklist 1647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if necessary. If the origLabel is a "special" label, it 1648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is returned exactly and not scheduled for duplication: copying 1649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * never proceeds past a special label, which likely is the function 1650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * return block or an immediate predecessor. 1651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param origLabel label of original, pre-copied block 1653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return label for new, inlined block 1654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int mapOrAllocateLabel(int origLabel) { 1656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int resultLabel; 1657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Integer mappedLabel = origLabelToCopiedLabel.get(origLabel); 1658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (mappedLabel != null) { 1660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLabel = mappedLabel; 1661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!involvedInSubroutine(origLabel,subroutineStart)) { 1662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A subroutine has ended by some means other than a "ret" 1664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (which really means a throw caught later). 1665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLabel = origLabel; 1667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLabel = labelAllocator.getNextLabel(); 1669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workList.set(origLabel); 1670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project origLabelToCopiedLabel.put(origLabel, resultLabel); 1671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The new label has the same frame as the original label 1673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (labelToSubroutines.size() <= resultLabel) { 1674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.add(null); 1675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.set(resultLabel, 1677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.get(origLabel)); 1678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultLabel; 1681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 168539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Finds a {@code Subroutine} that is returned from by a {@code ret} in 1686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a given block. 168739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 168839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param label A block that originally contained a {@code ret} instruction 168939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @return {@code null-ok;} found subroutine or {@code null} if none 169039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * was found 1691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Subroutine subroutineFromRetBlock(int label) { 1693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = subroutines.length - 1 ; i >= 0 ; i--) { 1694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines[i] != null) { 1695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine subroutine = subroutines[i]; 1696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutine.retBlocks.get(label)) { 1698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return subroutine; 1699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 1704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 170839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Removes all {@code move-return-address} instructions, returning a new 170939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code InsnList} if necessary. The {@code move-return-address} 171039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * insns are dead code after subroutines have been inlined. 1711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 171239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param insns {@code InsnList} that may contain 171339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code move-return-address} insns 171439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @return {@code InsnList} with {@code move-return-address} removed 1715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private InsnList filterMoveReturnAddressInsns(InsnList insns) { 1717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz; 1718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSz = 0; 1719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // First see if we need to filter, and if so what the new size will be 1721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sz = insns.size(); 1722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 1723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) { 1724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSz++; 1725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newSz == sz) { 1729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return insns; 1730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Make a new list without the MOVE_RETURN_ADDRESS insns 1733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList newInsns = new InsnList(newSz); 1734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newIndex = 0; 1736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 1737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = insns.get(i); 1738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) { 1739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newInsns.set(newIndex++, insn); 1740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newInsns.setImmutable(); 1744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newInsns; 1745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Visits each non-subroutine block once in depth-first successor order. 174939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param firstLabel label of start block 1751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param v callback interface 1752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 175339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein private void forEachNonSubBlockDepthFirst(int firstLabel, 175439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein BasicBlock.Visitor v) { 1755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel), 1756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v, new BitSet(maxLabel)); 1757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 176039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Visits each block once in depth-first successor order, ignoring 176139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code jsr} targets. Worker for {@link #forEachNonSubBlockDepthFirst}. 176239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param next next block to visit 1764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param v callback interface 1765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param visited set of blocks already visited 1766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void forEachNonSubBlockDepthFirst0( 1768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock next, BasicBlock.Visitor v, BitSet visited) { 1769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v.visitBlock(next); 1770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visited.set(next.getLabel()); 1771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = next.getSuccessors(); 1773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = successors.size(); 1774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 177539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein for (int i = 0; i < sz; i++) { 1776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succ = successors.get(i); 1777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (visited.get(succ)) { 1779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 1780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(next) && i > 0) { 1783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ignore jsr targets 1784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 1785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Ignore missing labels: they're successors of 1789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutines that never invoke a ret. 1790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(succ); 1792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx >= 0) { 1793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst0(result.get(idx), v, visited); 1794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 1798