Mercurial > hg > icedrobot > daneel
changeset 66:7ce7ce3d84fc
Implemented rewriting of AGET, AGET_WIDE, AGET_OBJECT, AGET_BOOLEAN, AGET_BYTE, AGET_CHAR and AGET_SHORT
Contributed-by: Remi Forax
rewriter/DexRewriter.java
Renamed arbitrary to untyped.
(getTypeFromASMType): Handle Type.ARRAY.
(getNewArrayKindFromASMType): Implemented.
(visitInstrClass): Handle when typeDesc!=OBJECT_TYPE.
(visitInstrMethod): Likewise.
(visitInstrNewArray): Implemented.
(visitInstrArray): Likewise.
rewriter/Interpreter.java:
Renamed arbitrary to untyped.
(storeUntypedType): Renamed from storeArbitraryType.
rewriter/Register.java:
Written Javadoc, renamed arbitrary to untyped.
(isUntyped): renamed from isArbitrary.
(makeArray): Implemented.
(isArray): Implemented.
(getArrayDimension): Implemented.
(getComponentType): Implemented.
(asDefaultTypedType): Renamed from asRuntimeType.
(getJavaOpcode): Handle if isArray.
(toString(int type)): Implemented based on toString.
author | Xerxes R?nby <xerxes@zafena.se> |
---|---|
date | Tue, 22 Mar 2011 17:55:09 +0100 |
parents | 3a01108d39d2 |
children | d1f8574aede4 |
files | src/main/java/org/icedrobot/daneel/rewriter/DexRewriter.java src/main/java/org/icedrobot/daneel/rewriter/Interpreter.java src/main/java/org/icedrobot/daneel/rewriter/Register.java |
diffstat | 3 files changed, 279 insertions(+), 63 deletions(-) [+] |
line wrap: on
line diff
--- a/src/main/java/org/icedrobot/daneel/rewriter/DexRewriter.java Tue Mar 22 17:08:24 2011 +0100 +++ b/src/main/java/org/icedrobot/daneel/rewriter/DexRewriter.java Tue Mar 22 17:55:09 2011 +0100 @@ -203,8 +203,35 @@ return DOUBLE_TYPE; case Type.VOID: return VOID_TYPE; + case Type.OBJECT: + return OBJECT_TYPE; + case Type.ARRAY: + return Register.makeArray(getTypeFromASMType(type.getElementType()), type.getDimensions()); default: - return OBJECT_TYPE; + throw new AssertionError("bad type "+type); + } + } + + private static int getNewArrayKindFromASMType(Type type) { + switch (type.getSort()) { + case Type.BOOLEAN: + return T_BOOLEAN; + case Type.BYTE: + return T_BYTE; + case Type.CHAR: + return T_CHAR; + case Type.SHORT: + return T_SHORT; + case Type.INT: + return T_INT; + case Type.LONG: + return T_LONG; + case Type.FLOAT: + return T_FLOAT; + case Type.DOUBLE: + return T_DOUBLE; + default: + throw new AssertionError("bad type "+type); } } @@ -328,17 +355,17 @@ } @Override - public void visitInstrClass(Opcode opcode, int vsrcOrDest, String type) { + public void visitInstrClass(Opcode opcode, int vsrcOrDest, String typeDesc) { vsrcOrDest = registerToSlot(vsrcOrDest); switch(opcode) { case CONST_CLASS: - mv.visitLdcInsn(Type.getType(type)); + mv.visitLdcInsn(Type.getType(typeDesc)); mv.visitVarInsn(ASTORE, vsrcOrDest); interpreter.store(vsrcOrDest, OBJECT_TYPE); break; case NEW_INSTANCE: mv.visitTypeInsn(NEW, TypeUtil - .convertDescToInternal(type)); + .convertDescToInternal(typeDesc)); mv.visitVarInsn(ASTORE, vsrcOrDest); interpreter.store(vsrcOrDest, OBJECT_TYPE); break; @@ -346,9 +373,9 @@ mv.visitVarInsn(ALOAD, vsrcOrDest); interpreter.load(vsrcOrDest, OBJECT_TYPE); mv.visitTypeInsn(CHECKCAST, TypeUtil - .convertDescToInternal(type)); + .convertDescToInternal(typeDesc)); mv.visitVarInsn(ASTORE, vsrcOrDest); - interpreter.store(vsrcOrDest, OBJECT_TYPE); + interpreter.store(vsrcOrDest, getTypeFromASMType(Type.getType(typeDesc))); break; default: throw newAssertionError(opcode); @@ -393,7 +420,7 @@ default: throw newAssertionError(opcode); } - + // We need to load the receiver first. int r; if (erasedRangeOpcode != Opcode.INVOKE_STATIC) { @@ -401,11 +428,11 @@ int register = registerToSlot((registers == null) ? va : registers[0]); mv.visitVarInsn(ALOAD, register); - interpreter.load(register, OBJECT_TYPE); + interpreter.load(register, getTypeFromASMType(Type.getType(owner))); } else { r = 0; } - + Type[] types = Type.getArgumentTypes(desc); for (Type asmType : types) { int type = getTypeFromASMType(asmType); @@ -435,7 +462,7 @@ final AbstractInsnNode ldc = mv.getLastInsnNode(); mv.visitVarInsn(ISTORE, sdest); final AbstractInsnNode istore = mv.getLastInsnNode(); - interpreter.storeArbitraryType(sdest, U32_TYPE, new Patchable() { + interpreter.storeUntypedType(sdest, U32_TYPE, new Patchable() { @Override protected void patch(int registerType) { if (registerType == FLOAT_TYPE) { @@ -456,7 +483,7 @@ final AbstractInsnNode ldc = mv.getLastInsnNode(); mv.visitVarInsn(LSTORE, sdest); final AbstractInsnNode lstore = mv.getLastInsnNode(); - interpreter.storeArbitraryType(sdest, U64_TYPE, new Patchable() { + interpreter.storeUntypedType(sdest, U64_TYPE, new Patchable() { @Override protected void patch(int registerType) { if (registerType == DOUBLE_TYPE) { @@ -496,7 +523,7 @@ throw new UnsupportedOperationException("NYI " + opcode); } } - + @Override public void visitInstrUnaryOp(Opcode opcode, int dest, int src) { final int vdest = registerToSlot(dest); @@ -514,15 +541,15 @@ case MOVE_OBJECT_16: { final Register register = interpreter.getRegister(vsrc); int type = register.getType(); - if (Register.isArbitrary(type)) { - int runtimeType = Register.asRuntimeType(type); + if (Register.isUntyped(type)) { + int runtimeType = Register.asDefaultTypedType(type); mv.setPatchMode(); mv.visitVarInsn(Register.getJavaOpcode(runtimeType, ILOAD), vsrc); final AbstractInsnNode load = mv.getLastInsnNode(); mv.visitVarInsn(Register.getJavaOpcode(runtimeType, ISTORE), vdest); final AbstractInsnNode store = mv.getLastInsnNode(); final Patchable patchable = register.getPatchable(); - interpreter.storeArbitraryType(vdest, type, new Patchable() { + interpreter.storeUntypedType(vdest, type, new Patchable() { @Override protected void patch(int registerType) { patchable.doPatch(registerType); @@ -663,6 +690,51 @@ mv.visitJumpInsn(toJavaOpcode[opcode.ordinal()], asmLabel); } + @Override + public void visitInstrNewArray(Opcode opcode, int vdest, int vsize, + String typeDesc) { + vdest = registerToSlot(vdest); + vsize = registerToSlot(vsize); + + mv.visitVarInsn(ILOAD, vsize); + interpreter.load(vsize, INT_TYPE); + mv.visitIntInsn(NEWARRAY, getNewArrayKindFromASMType(Type.getType(typeDesc).getElementType())); + mv.visitVarInsn(ASTORE, vdest); + interpreter.store(vdest, getTypeFromASMType(Type.getType(typeDesc))); + } + + @Override + public void visitInstrArray(Opcode opcode, int vsrcOrDest, int varray, + int vindex) { + vsrcOrDest = registerToSlot(vsrcOrDest); + varray = registerToSlot(varray); + vindex = registerToSlot(vindex); + + int type = interpreter.getRegister(varray).getType(); + int componentType = Register.getComponentType(type); + interpreter.load(vindex, INT_TYPE); + + switch(opcode) { + case APUT: case APUT_WIDE: case APUT_OBJECT: + case APUT_BOOLEAN: case APUT_BYTE: case APUT_CHAR: case APUT_SHORT: + mv.visitVarInsn(Register.getJavaOpcode(type, ILOAD), varray); + mv.visitVarInsn(ILOAD, vindex); + mv.visitVarInsn(Register.getJavaOpcode(componentType, ILOAD), vsrcOrDest); + mv.visitInsn(Register.getJavaOpcode(componentType, IASTORE)); + interpreter.load(vsrcOrDest, componentType); + break; + default: + //case AGET: case AGET_WIDE: case AGET_OBJECT: + //case AGET_BOOLEAN: case AGET_BYTE: case AGET_CHAR: case AGET_SHORT: + mv.visitVarInsn(Register.getJavaOpcode(type, ILOAD), varray); + mv.visitVarInsn(ILOAD, vindex); + mv.visitInsn(Register.getJavaOpcode(componentType, IALOAD)); + mv.visitVarInsn(Register.getJavaOpcode(componentType, ISTORE), vsrcOrDest); + interpreter.store(vsrcOrDest, componentType); + break; + } + } + // unimplemented @@ -675,13 +747,6 @@ } @Override - public void visitInstrArray(Opcode opcode, int vsrcOrDest, int varray, - int vindex) { - vsrcOrDest = registerToSlot(vsrcOrDest); - throw new UnsupportedOperationException("NYI " + opcode); - } - - @Override public void visitInstrFillArrayData(Opcode opcode, int vsrc, Object arrayData) { vsrc = registerToSlot(vsrc); @@ -704,13 +769,6 @@ } @Override - public void visitInstrNewArray(Opcode opcode, int vdest, int vsize, - String type) { - vdest = registerToSlot(vdest); - throw new UnsupportedOperationException("NYI " + opcode); - } - - @Override public void visitInstrSwitch(Opcode opcode, int vsrc, Map<Integer, Label> labels) { vsrc = registerToSlot(vsrc);
--- a/src/main/java/org/icedrobot/daneel/rewriter/Interpreter.java Tue Mar 22 17:08:24 2011 +0100 +++ b/src/main/java/org/icedrobot/daneel/rewriter/Interpreter.java Tue Mar 22 17:55:09 2011 +0100 @@ -73,12 +73,12 @@ /** * Tracks a load operation on the given register. The expected type has to - * be a concrete (non-arbitrary) type. This might trigger the register to - * change from an arbitrary to the given concrete type and in turn trigger + * be a concrete (non-untyped) type. This might trigger the register to + * change from an untyped to the given concrete type and in turn trigger * operation patching. * * @param vregister The register number of a tracked register. - * @param expectedType The expected (non-arbitrary) type of the register. + * @param expectedType The expected (non-untyped) type of the register. */ public void load(int vregister, int expectedType) { registers[vregister] = registers[vregister].load(expectedType); @@ -86,37 +86,37 @@ /** * Tracks a store operation on the given register. The expected type has to - * be a concrete (non-arbitrary) type. The previous content of the given + * be a concrete (non-untyped) type. The previous content of the given * register will be destroyed. * * @param vregister The register number of a tracked register. - * @param type The (non-arbitrary) type of the operation. + * @param type The (non-untyped) type of the operation. */ public void store(int vregister, int type) { - if (Register.isArbitrary(type)) { + if (Register.isUntyped(type)) { throw new IllegalArgumentException("invalid type"); } - + registers[vregister] = new Register(type, null); } /** - * Tracks an arbitrary typed store operation on the given register. Since + * Tracks an untyped typed store operation on the given register. Since * the operation is not yet concretely typed, the operation has to be * "patchable" to change it's type later on. The previous content of the * given register will be destroyed. * * @param vregister The register number of a tracked register. - * @param arbitraryType The (arbitrary) type of the operation. + * @param untypedType The (untyped) type of the operation. * @param patchable The patcher to change the operation type. */ - public void storeArbitraryType(int vregister, int arbitraryType, + public void storeUntypedType(int vregister, int untypedType, Patchable patchable) { - if (!Register.isArbitrary(arbitraryType)) { + if (!Register.isUntyped(untypedType)) { throw new IllegalArgumentException("invalid type"); } - - registers[vregister] = new Register(arbitraryType, patchable); + + registers[vregister] = new Register(untypedType, patchable); } /**
--- a/src/main/java/org/icedrobot/daneel/rewriter/Register.java Tue Mar 22 17:08:24 2011 +0100 +++ b/src/main/java/org/icedrobot/daneel/rewriter/Register.java Tue Mar 22 17:55:09 2011 +0100 @@ -39,9 +39,40 @@ import org.objectweb.asm.Opcodes; +/** + * A virtual register of the abstract interpreter. + * + * The field type is a 32bits value encoded as follow: + * 0-7 8-15 16-30 31 + * type kind dimension garbage isUntyped + * + * Some Dalvik opcodes don't have variant for int and float + * (resp. long and double). Only one opcode is use and corresponding + * register is viewed as plain a 32bits value (resp. 64bits value). + * The JVM opcodes always specifies different variant of a same opcode + * for types that have the same size in bits. + * + * So the rewriter as to perform an analysis of the use of this kind of register + * to infer if it's by example a 32bits int or a 32bits float. + * This register are typed U32 (resp. U64) for Untyped 32bits value (64bits value). + * + * NO_TYPE represents the type of a register that is not yet initialized. + * It is categorized as untyped because it seems more simple from + * the code point of view. + * + * This class is mostly non mutable, but {@link Patchable} is mutable to allow + * to change the type of an U32 (resp. U64) to its infered type, + * see {@link #getType()} for more info. + * + * A patchable is a callback that will be called when the type of an untyped register + * is infered. This allow to patch the instructions stream to use the JVM opcode + * corresponding to the inferred type. + * As an invariant only U32 and U64 can have a non null {@link Patchable}. + * + */ public class Register { - // the order is the same order as java bytecode IALOAD/IASTORE order (see - // #getJavaOpcode) + // the order is the same order as java bytecode IALOAD/IASTORE order + // (see #getJavaOpcode) public static final int INT_TYPE = 0; // signed int public static final int LONG_TYPE = 1; // signed long public static final int FLOAT_TYPE = 2; // 32 bits float @@ -53,12 +84,12 @@ public static final int BOOLEAN_TYPE = 8; // boolean public static final int VOID_TYPE = 9; // void, added to simplify management - public static final int U32_TYPE = -1; // arbitrary 32bits constant - public static final int U64_TYPE = -2; // arbitrary 64bits constant + public static final int U32_TYPE = -1; // untyped 32bits constant + public static final int U64_TYPE = -2; // untyped 64bits constant public static final int NO_TYPE = -3; // unassigned register - private static final int ARBITRARY_MASK = Integer.MIN_VALUE; + private static final int UNTYPED_MASK = Integer.MIN_VALUE; static final Register UNINITIALIZED = new Register(NO_TYPE, null); @@ -71,6 +102,12 @@ this.patchable = patchable; } + /** Returns the type of the current register. + * The type of an untyped register is not constant and + * may be changed to its infered type. + * + * @return the type of the current register. + */ public int getType() { if (patchable != null) { int patchableType = patchable.getType(); @@ -78,13 +115,24 @@ } return type; } - + + /** Returns the callback associated with this register. + * As an invariant only register typed U32 and U64 can have a non null {@link Patchable}. + * @return the callback assocaited with this register or null otherwise. + */ public Patchable getPatchable() { return patchable; } - + + /** Simulate a load from the current register. + * If the type of the current register is {@link #isUntyped(int) untyped} + * the corresponding {@link Patchable patchable} will be called. + * + * @param expectedType the expected type of the register + * @return a new register with the expected type + */ public Register load(int expectedType) { - if (isArbitrary(expectedType)) { + if (isUntyped(expectedType)) { throw new IllegalArgumentException("invalid type"); } @@ -94,6 +142,23 @@ return new Register(expectedType, null); } + /** Merge two registers and compute the type of the resulting register. + * + * The algorithme works as follow: + * <ul> + * <li>If one of the registers is uninitialized ({@link #NO_TYPE}), + * the type of the resulting register will be the type of the other. + * <li>If one of the registers is {@link #isUntyped(int) untyped}, + * the type of the resulting register will be the type of the other. + * If the two register are untyped, the new register will do + * the union of the two patchables. + * <li>Otherwise, if the intruction flow is not ill-formed, the + * types of the two registers should be the same. + * </ul> + * + * @param register the second register (this is the first one). + * @return a new register with a type corresponding + */ public Register merge(Register register) { int thisType = getType(); int registerType = register.getType(); @@ -105,11 +170,11 @@ return this; } - boolean thisIsArbitrary = isArbitrary(thisType); - boolean registerIsArbitrary = isArbitrary(registerType); + boolean thisIsUntyped = isUntyped(thisType); + boolean registerIsUntyped = isUntyped(registerType); - if (thisIsArbitrary) { - if (registerIsArbitrary) { + if (thisIsUntyped) { + if (registerIsUntyped) { // maybe there are not compatible, but this means that // the code is malformed return new Register(thisType, Patchable.union(patchable, register.patchable)); @@ -120,10 +185,10 @@ return new Register(registerType, null); } - // the two register aren't arbitrary, we don't check is they are compatible + // the two register aren't untyped, we don't check is they are compatible // because they can be incompatible if the register is no more used // This should not be the common case because dx remove unused registers - if (!registerIsArbitrary) { + if (!registerIsUntyped) { return this; } @@ -133,20 +198,96 @@ return new Register(thisType, null); } - public static boolean isArbitrary(int type) { - return (type & ARBITRARY_MASK) != 0; + /** Returns true is the register is untyped. + * {@link #U32_TYPE}, {@link #U64_TYPE} and {@link #NO_TYPE} + * are untyped. + * @param type register type to test + * @return true if the register type is untyped. + */ + public static boolean isUntyped(int type) { + return (type & UNTYPED_MASK) != 0; + } + + /** Create the type of an array of type. + * @param elementType the element type of the array (which can't be an array itself) + * @param dimension the dimension of the array. As in Java or Dalvik, the dimension + * is limited to 255. + * @return the corresponding array type. + */ + public static int makeArray(int elementType, int dimension) { + if (isUntyped(elementType) || isArray(elementType)) { + throw new IllegalArgumentException("invalid type"); + } + return dimension << 8 | (elementType & 0xFF); + } + + /** Returns true if the type is an array type. + * @param type the type that can be an array type. + * @return true if the type is an array type. + */ + public static boolean isArray(int type) { + return ((type >> 8) & 0xFF) != 0; + } + + /** Returns the array dimension of the type that must be an array. + * @param type an array type + * @return the array dimension of the array type. + * @throws IllegalArgumentException is the type is not an array type. + * @see #isArray(int) + */ + public static int getArrayDimension(int type) { + if (!isArray(type)) { + throw new IllegalArgumentException("type is not an array"); + } + return (type >> 8) & 0xFF; + } + + /** Returns the component type of the type that must be an array. + * The component type has the same element type as the array type + * and a dimension decremented by one. + * @param type an array type. + * @return the component type of the array. + * @throws IllegalArgumentException is the type is not an array type. + */ + public static int getComponentType(int type) { + if (!isArray(type)) { + throw new IllegalArgumentException("type is not an array"); + } + return ((((type >> 8) & 0xFF) -1 ) << 8) | (type & 0xFF); } - public static int asRuntimeType(int type) { - return (type == LONG_TYPE || type == DOUBLE_TYPE) ? LONG_TYPE - : INT_TYPE; + /** Return the type (typed) used to represent an untyped type + * before patching occurs. + * For {@link #U32_TYPE} the corresponding type is {@link #INT_TYPE}, + * for {@link #U64_TYPE} the corresponding type is {@link #LONG_TYPE}, + * + * @param type an untyped type + * @return the corresponding type. + */ + public static int asDefaultTypedType(int type) { + if (!isUntyped(type)) { + throw new IllegalArgumentException("invalid type"); + } + return (type == U64_TYPE) ? LONG_TYPE: INT_TYPE; } + /** Returns the JVM opcode from a type and a base opcode. + * @param type a type + * @param opcode a base opcode among ILOAD, ISTORE, + * IADD, ISUB, IMUL, IDIV, IREM, INEG, ISHL, + * ISHR, IUSHR, IAND, IOR, IXOR, IRETURN, + * IALOAD, IASTORE. + * @return the variant opcode corresponding to the type. + */ public static int getJavaOpcode(int type, int opcode) { - if (isArbitrary(type)) { + if (isUntyped(type)) { throw new IllegalArgumentException("invalid type"); } + if (isArray(type)) { + type = OBJECT_TYPE; + } + if (opcode == Opcodes.IALOAD || opcode == Opcodes.IASTORE) { return opcode + ((type != BOOLEAN_TYPE) ? type : BYTE_TYPE); } @@ -157,6 +298,14 @@ @Override public String toString() { + return toString(type); + } + + /** Returns a string representation of the register type. + * @param type a register type + * @return a string representation of the register type. + */ + private static String toString(int type) { switch (type) { case OBJECT_TYPE: return "object"; @@ -175,6 +324,15 @@ case NO_TYPE: return "uninitialized"; } - throw new AssertionError(); + if (!isArray(type)) { + throw new AssertionError(); + } + + int dimension = getArrayDimension(type); + StringBuilder builder = new StringBuilder(dimension + 6); + for(int i=0; i<dimension; i++) { + builder.append('['); + } + return builder.append(toString(type & 0xFF)).toString(); } }