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.ssa; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhaoimport com.android.dx.rop.code.PlainCstInsn; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.TranslationAdvice; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecList; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Insn; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Rop; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.PlainInsn; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Rops; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegOps; 28b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhaoimport com.android.dx.rop.cst.Constant; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstLiteralBits; 30b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhaoimport com.android.dx.rop.type.Type; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.TypeBearer; 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 33e1c3a8e2203881759efec3538cc654937de1d817jeffhaoimport java.util.ArrayList; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.List; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 37ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson * Upgrades insn to their literal (constant-immediate) equivalent if possible. 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Also switches IF instructions that compare with a constant zero or null 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to be their IF_*Z equivalents. 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class LiteralOpUpgrader { 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** method we're processing */ 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final SsaMethod ssaMeth; 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Process a method. 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param ssaMethod {@code non-null;} method to process 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static void process(SsaMethod ssaMethod) { 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LiteralOpUpgrader dc; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dc = new LiteralOpUpgrader(ssaMethod); 55de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dc.run(); 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private LiteralOpUpgrader(SsaMethod ssaMethod) { 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.ssaMeth = ssaMethod; 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if the register contains an integer 0 or a known-null 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * object reference 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param spec non-null spec 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true for 0 or null type bearers 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean isConstIntZeroOrKnownNull(RegisterSpec spec) { 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypeBearer tb = spec.getTypeBearer(); 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (tb instanceof CstLiteralBits) { 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstLiteralBits clb = (CstLiteralBits) tb; 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (clb.getLongBits() == 0); 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Run the literal op upgrader 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void run() { 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final TranslationAdvice advice = Optimizer.getAdvice(); 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.forEachInsn(new SsaInsn.Visitor() { 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn(NormalSsaInsn insn) { 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // do nothing 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn(PhiInsn insn) { 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // do nothing 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn(NormalSsaInsn insn) { 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn originalRopInsn = insn.getOriginalRopInsn(); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop opcode = originalRopInsn.getOpcode(); 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 100b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao // Replace insns with constant results with const insns 101e1c3a8e2203881759efec3538cc654937de1d817jeffhao if (tryReplacingWithConstant(insn)) return; 102b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (sources.size() != 2 ) { 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We're only dealing with two-source insns here. 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (opcode.getBranchingness() == Rop.BRANCH_IF) { 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * An if instruction can become an if-*z instruction. 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isConstIntZeroOrKnownNull(sources.get(0))) { 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project replacePlainInsn(insn, sources.withoutFirst(), 114b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao RegOps.flippedIfOpcode(opcode.getOpcode()), null); 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (isConstIntZeroOrKnownNull(sources.get(1))) { 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project replacePlainInsn(insn, sources.withoutLast(), 117b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao opcode.getOpcode(), null); 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (advice.hasConstantOperation( 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project opcode, sources.get(0), sources.get(1))) { 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.upgradeToLiteral(); 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (opcode.isCommutative() 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && advice.hasConstantOperation( 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project opcode, sources.get(1), sources.get(0))) { 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * An instruction can be commuted to a literal operation 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setNewSources( 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make( 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sources.get(1), sources.get(0))); 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.upgradeToLiteral(); 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 140e1c3a8e2203881759efec3538cc654937de1d817jeffhao * Tries to replace an instruction with a const instruction. The given 141e1c3a8e2203881759efec3538cc654937de1d817jeffhao * instruction must have a constant result for it to be replaced. 142e1c3a8e2203881759efec3538cc654937de1d817jeffhao * 143e1c3a8e2203881759efec3538cc654937de1d817jeffhao * @param insn {@code non-null;} instruction to try to replace 144e1c3a8e2203881759efec3538cc654937de1d817jeffhao * @return true if the instruction was replaced 145e1c3a8e2203881759efec3538cc654937de1d817jeffhao */ 146e1c3a8e2203881759efec3538cc654937de1d817jeffhao private boolean tryReplacingWithConstant(NormalSsaInsn insn) { 147e1c3a8e2203881759efec3538cc654937de1d817jeffhao Insn originalRopInsn = insn.getOriginalRopInsn(); 148e1c3a8e2203881759efec3538cc654937de1d817jeffhao Rop opcode = originalRopInsn.getOpcode(); 14938b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao RegisterSpec result = insn.getResult(); 150e1c3a8e2203881759efec3538cc654937de1d817jeffhao 15138b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao if (result != null && !ssaMeth.isRegALocal(result) && 15238b61748553bd387bc36b6bd82a8667b6c5f5934jeffhao opcode.getOpcode() != RegOps.CONST) { 153e1c3a8e2203881759efec3538cc654937de1d817jeffhao TypeBearer type = insn.getResult().getTypeBearer(); 154e1c3a8e2203881759efec3538cc654937de1d817jeffhao if (type.isConstant() && type.getBasicType() == Type.BT_INT) { 155e1c3a8e2203881759efec3538cc654937de1d817jeffhao // Replace the instruction with a constant 156e1c3a8e2203881759efec3538cc654937de1d817jeffhao replacePlainInsn(insn, RegisterSpecList.EMPTY, 157e1c3a8e2203881759efec3538cc654937de1d817jeffhao RegOps.CONST, (Constant) type); 158e1c3a8e2203881759efec3538cc654937de1d817jeffhao 159e1c3a8e2203881759efec3538cc654937de1d817jeffhao // Remove the source as well if this is a move-result-pseudo 160e1c3a8e2203881759efec3538cc654937de1d817jeffhao if (opcode.getOpcode() == RegOps.MOVE_RESULT_PSEUDO) { 161e1c3a8e2203881759efec3538cc654937de1d817jeffhao int pred = insn.getBlock().getPredecessors().nextSetBit(0); 162e1c3a8e2203881759efec3538cc654937de1d817jeffhao ArrayList<SsaInsn> predInsns = 163e1c3a8e2203881759efec3538cc654937de1d817jeffhao ssaMeth.getBlocks().get(pred).getInsns(); 164e1c3a8e2203881759efec3538cc654937de1d817jeffhao NormalSsaInsn sourceInsn = 165e1c3a8e2203881759efec3538cc654937de1d817jeffhao (NormalSsaInsn) predInsns.get(predInsns.size()-1); 166e1c3a8e2203881759efec3538cc654937de1d817jeffhao replacePlainInsn(sourceInsn, RegisterSpecList.EMPTY, 167e1c3a8e2203881759efec3538cc654937de1d817jeffhao RegOps.GOTO, null); 168e1c3a8e2203881759efec3538cc654937de1d817jeffhao } 169e1c3a8e2203881759efec3538cc654937de1d817jeffhao return true; 170e1c3a8e2203881759efec3538cc654937de1d817jeffhao } 171e1c3a8e2203881759efec3538cc654937de1d817jeffhao } 172e1c3a8e2203881759efec3538cc654937de1d817jeffhao return false; 173e1c3a8e2203881759efec3538cc654937de1d817jeffhao } 174e1c3a8e2203881759efec3538cc654937de1d817jeffhao 175e1c3a8e2203881759efec3538cc654937de1d817jeffhao /** 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replaces an SsaInsn containing a PlainInsn with a new PlainInsn. The 177b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao * new PlainInsn is constructed with a new RegOp and new sources. 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * TODO move this somewhere else. 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 18199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} an SsaInsn containing a PlainInsn 18299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param newSources {@code non-null;} new sources list for new insn 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newOpcode A RegOp from {@link RegOps} 184b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao * @param cst {@code null-ok;} constant for new instruction, if any 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void replacePlainInsn(NormalSsaInsn insn, 187b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao RegisterSpecList newSources, int newOpcode, Constant cst) { 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn originalRopInsn = insn.getOriginalRopInsn(); 190b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao Rop newRop = Rops.ropFor(newOpcode, insn.getResult(), newSources, cst); 191b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao Insn newRopInsn; 192b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao if (cst == null) { 193b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao newRopInsn = new PlainInsn(newRop, originalRopInsn.getPosition(), 194b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao insn.getResult(), newSources); 195b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } else { 196b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao newRopInsn = new PlainCstInsn(newRop, originalRopInsn.getPosition(), 197b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao insn.getResult(), newSources, cst); 198b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao } 199b75d1ca580c6a6c7ebdc813dff2855205063fc46jeffhao NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project List<SsaInsn> insns = insn.getBlock().getInsns(); 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.onInsnRemoved(insn); 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(insns.lastIndexOf(insn), newInsn); 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ssaMeth.onInsnAdded(newInsn); 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 208