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 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.BasicBlockList; 20e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Insn; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.PlainInsn; 22e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.RegOps; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecList; 25e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Rop; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RopMethod; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Rops; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.SourcePosition; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Collections; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.List; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Set; 36e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport java.util.Stack; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 39d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * A method in SSA form. 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class SsaMethod { 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** basic blocks, indexed by block index */ 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ArrayList<SsaBasicBlock> blocks; 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Index of first executed block in method */ 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int entryBlockIndex; 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Index of exit block, which exists only in SSA form, 50d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * or or {@code -1} if there is none 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int exitBlockIndex; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 54d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /** total number of registers required */ 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int registerCount; 56d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 57d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /** first register number to use for any temporary "spares" */ 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int spareRegisterBase; 59d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 60d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /** current count of spare registers used */ 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int borrowedSpareRegisters; 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** really one greater than the max label */ 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int maxLabel; 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** the total width, in register-units, of the method's parameters */ 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int paramWidth; 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /** true if this method has no {@code this} pointer argument */ 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final boolean isStatic; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * indexed by register: the insn where said register is defined or null 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if undefined. null until (lazily) created. 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private SsaInsn[] definitionList; 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** indexed by register: the list of all insns that use a register */ 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ArrayList<SsaInsn>[] useList; 80f7c7608d758bf7e30875f379858cc765a17d6d49Dan Bornstein 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** A version of useList with each List unmodifiable */ 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private List<SsaInsn>[] unmodifiableUseList; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * "back-convert mode". Set during back-conversion when registers 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are about to be mapped into a non-SSA namespace. When true, 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * use and def lists are unavailable. 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 89d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * TODO: Remove this mode, and place the functionality elsewhere 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 91d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein private boolean backMode; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 94d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param ropMethod rop-form method to convert from 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param paramWidth the total width, in register-units, of the 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method's parameters 97d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param isStatic {@code true} if this method has no {@code this} 98d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * pointer argument 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 100d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein public static SsaMethod newFromRopMethod(RopMethod ropMethod, 101d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein int paramWidth, boolean isStatic) { 102d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein SsaMethod result = new SsaMethod(ropMethod, paramWidth, isStatic); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 104d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein result.convertRopToSsaBlocks(ropMethod); 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 110d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Constructs an instance. 111d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 112d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param ropMethod {@code non-null;} the original rop-form method that 113d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * this instance is based on 114d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param paramWidth the total width, in register-units, of the 115d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * method's parameters 116d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param isStatic {@code true} if this method has no {@code this} 117d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * pointer argument 118d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein */ 119d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein private SsaMethod(RopMethod ropMethod, int paramWidth, boolean isStatic) { 120d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein this.paramWidth = paramWidth; 121d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein this.isStatic = isStatic; 122d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein this.backMode = false; 123d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein this.maxLabel = ropMethod.getBlocks().getMaxLabel(); 124d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein this.registerCount = ropMethod.getBlocks().getRegCount(); 125d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein this.spareRegisterBase = registerCount; 126d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein } 127d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 128d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /** 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Builds a BitSet of block indices from a basic block list and a list 130d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * of labels taken from Rop form. 131d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param blocks Rop blocks 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param labelList list of rop block labels 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return BitSet of block indices 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static BitSet bitSetFromLabelList(BasicBlockList blocks, 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList labelList) { 138d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein BitSet result = new BitSet(blocks.size()); 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 140d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein for (int i = 0, sz = labelList.size(); i < sz; i++) { 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.set(blocks.indexOfLabel(labelList.get(i))); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Builds an IntList of block indices from a basic block list and a list 149d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * of labels taken from Rop form. 150d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ropBlocks Rop blocks 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param labelList list of rop block labels 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return IntList of block indices 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static IntList indexListFromLabelList(BasicBlockList ropBlocks, 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList labelList) { 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 158d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein IntList result = new IntList(labelList.size()); 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 160d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein for (int i = 0, sz = labelList.size(); i < sz; i++) { 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(ropBlocks.indexOfLabel(labelList.get(i))); 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 167d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein private void convertRopToSsaBlocks(RopMethod rmeth) { 168d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein BasicBlockList ropBlocks = rmeth.getBlocks(); 169d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein int sz = ropBlocks.size(); 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 171d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein blocks = new ArrayList<SsaBasicBlock>(sz + 2); 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 173d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein for (int i = 0; i < sz; i++) { 174d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein SsaBasicBlock sbb = SsaBasicBlock.newFromRop(rmeth, i, this); 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project blocks.add(sbb); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 178d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein // Add an no-op entry block. 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origEntryBlockIndex = rmeth.getBlocks() 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .indexOfLabel(rmeth.getFirstLabel()); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock entryBlock 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = blocks.get(origEntryBlockIndex).insertNewPredecessor(); 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project entryBlockIndex = entryBlock.getIndex(); 186d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein exitBlockIndex = -1; // This gets made later. 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Creates an exit block and attaches it to the CFG if this method 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * exits. Methods that never exit will not have an exit block. This 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is called after edge-splitting and phi insertion, since the edges 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * going into the exit block should not be considered in those steps. 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 195d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /*package*/ void makeExitBlock() { 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (exitBlockIndex >= 0) { 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("must be called at most once"); 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exitBlockIndex = blocks.size(); 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock exitBlock 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new SsaBasicBlock(exitBlockIndex, maxLabel++, this); 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project blocks.add(exitBlock); 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 20641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaBasicBlock block : blocks) { 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project block.exitBlockFixup(exitBlock); 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (exitBlock.getPredecessors().cardinality() == 0) { 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // In cases where there is no exit... 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project blocks.remove(exitBlockIndex); 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exitBlockIndex = -1; 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxLabel--; 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 219d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Gets a new {@code GOTO} insn. 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param block block to which this GOTO will be added 222d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * (not it's destination!) 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return an appropriately-constructed instance. 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static SsaInsn getGoto(SsaBasicBlock block) { 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new NormalSsaInsn ( 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new PlainInsn(Rops.GOTO, SourcePosition.NO_INFO, 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project null, RegisterSpecList.EMPTY), block); 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 230d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 232d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Makes a new basic block for this method, which is empty besides 233d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * a single {@code GOTO}. Successors and predecessors are not yet 234d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * set. 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return new block 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock makeNewGotoBlock() { 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newIndex = blocks.size(); 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock newBlock = new SsaBasicBlock(newIndex, maxLabel++, this); 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlock.getInsns().add(getGoto(newBlock)); 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project blocks.add(newBlock); 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newBlock; 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return block index of first execution block 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getEntryBlockIndex() { 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return entryBlockIndex; 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return first execution block 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock getEntryBlock() { 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return blocks.get(entryBlockIndex); 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 263d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @return block index of exit block or {@code -1} if there is none 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getExitBlockIndex() { 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return exitBlockIndex; 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 270d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @return {@code null-ok;} block of exit block or {@code null} if 271d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * there is none 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock getExitBlock() { 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return exitBlockIndex < 0 ? null : blocks.get(exitBlockIndex); 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 278d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param bi block index or {@code -1} for none 279d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @return rop label or {code -1} if {@code bi} was {@code -1} 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int blockIndexToRopLabel(int bi) { 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (bi < 0) { 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return blocks.get(bi).getRopLabel(); 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return count of registers used in this method 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getRegCount() { 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return registerCount; 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 296d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @return the total width, in register units, of the method's 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * parameters 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getParamWidth() { 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return paramWidth; 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 304d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Returns {@code true} if this is a static method. 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 306d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @return {@code true} if this is a static method 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean isStatic() { 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return isStatic; 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 313d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Borrows a register to use as a temp. Used in the phi removal process. 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Call returnSpareRegisters() when done. 315d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param category width (1 or 2) of the register 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return register number to use 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int borrowSpareRegister(int category) { 320d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein int result = spareRegisterBase + borrowedSpareRegisters; 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project borrowedSpareRegisters += category; 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project registerCount = Math.max(registerCount, result + category); 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns all borrowed registers. 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void returnSpareRegisters() { 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project borrowedSpareRegisters = 0; 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 336d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @return {@code non-null;} basic block list. Do not modify. 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public ArrayList<SsaBasicBlock> getBlocks() { 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return blocks; 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the count of reachable blocks in this method: blocks that have 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * predecessors (or are the start block) 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 34699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} number of reachable basic blocks 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getCountReachableBlocks() { 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ret = 0; 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 35141aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaBasicBlock b : blocks) { 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Blocks that have been disconnected don't count. 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (b.isReachable()) { 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret++; 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 362e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Computes reachability for all blocks in the method. First clears old 363e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * values from all blocks, then starts with the entry block and walks down 364e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * the control flow graph, marking all blocks it finds as reachable. 365e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 366e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void computeReachability() { 367e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (SsaBasicBlock block : blocks) { 368e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao block.setReachable(0); 369e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 370e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 371e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao ArrayList<SsaBasicBlock> blockList = new ArrayList<SsaBasicBlock>(); 372e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao blockList.add(this.getEntryBlock()); 373e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 374e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao while (!blockList.isEmpty()) { 375e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao SsaBasicBlock block = blockList.remove(0); 376e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (block.isReachable()) continue; 377e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 378e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao block.setReachable(1); 379e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao BitSet succs = block.getSuccessors(); 380e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (int i = succs.nextSetBit(0); i >= 0; 381e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao i = succs.nextSetBit(i + 1)) { 382e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao blockList.add(blocks.get(i)); 383e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 384e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 385e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 386e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 387e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Remaps unversioned registers. 389d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param mapper maps old registers to new. 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void mapRegisters(RegisterMapper mapper) { 393d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein for (SsaBasicBlock block : getBlocks()) { 39441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaInsn insn : block.getInsns()) { 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.mapRegisters(mapper); 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 397d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein } 398d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project registerCount = mapper.getNewRegisterCount(); 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project spareRegisterBase = registerCount; 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the insn that defines the given register 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param reg register in question 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return insn (actual instance from code) that defined this reg or null 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if reg is not defined. 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaInsn getDefinitionForRegister(int reg) { 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (backMode) { 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("No def list in back mode"); 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (definitionList != null) { 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return definitionList[reg]; 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList = new SsaInsn[getRegCount()]; 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachInsn(new SsaInsn.Visitor() { 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn (NormalSsaInsn insn) { 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList[insn.getResult().getReg()] = insn; 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn (PhiInsn phi) { 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList[phi.getResult().getReg()] = phi; 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn (NormalSsaInsn insn) { 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = insn.getResult(); 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result != null) { 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList[insn.getResult().getReg()] = insn; 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return definitionList[reg]; 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Builds useList and unmodifiableUseList. 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void buildUseList() { 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (backMode) { 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("No use list in back mode"); 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList = new ArrayList[registerCount]; 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 448d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein for (int i = 0; i < registerCount; i++) { 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList[i] = new ArrayList(); 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachInsn(new SsaInsn.Visitor() { 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitMoveInsn (NormalSsaInsn insn) { 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addToUses(insn); 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPhiInsn (PhiInsn phi) { 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addToUses(phi); 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitNonMoveInsn (NormalSsaInsn insn) { 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addToUses(insn); 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds specified insn to the uses list for all of its sources. 46799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to process 468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addToUses(SsaInsn insn) { 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList rl = insn.getSources(); 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = rl.size(); 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList[rl.get(i).getReg()].add(insn); 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unmodifiableUseList = new List[registerCount]; 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 481d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein for (int i = 0; i < registerCount; i++) { 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unmodifiableUseList[i] = Collections.unmodifiableList(useList[i]); 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Updates the use list for a single change in source register. 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 48999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn being changed 490d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param oldSource {@code null-ok;} The source that was used, if 491d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * applicable 49299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param newSource {@code non-null;} the new source being used 493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 494d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /*package*/ void onSourceChanged(SsaInsn insn, 495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec oldSource, RegisterSpec newSource) { 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (useList == null) return; 497d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldSource != null) { 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = oldSource.getReg(); 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList[reg].remove(insn); 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = newSource.getReg(); 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (useList.length <= reg) { 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList = null; 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList[reg].add(insn); 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Updates the use list for a source list change. 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 514d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param insn {@code insn non-null;} insn being changed. 515d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * {@code insn.getSources()} must return the new source list. 516d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param oldSources {@code null-ok;} list of sources that were 517d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * previously used 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 519d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /*package*/ void onSourcesChanged(SsaInsn insn, 520d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein RegisterSpecList oldSources) { 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (useList == null) return; 522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldSources != null) { 524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeFromUseList(insn, oldSources); 525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szNew = sources.size(); 529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 53041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int i = 0; i < szNew; i++) { 531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = sources.get(i).getReg(); 532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList[reg].add(insn); 533d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein } 534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 53799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Removes a given {@code insn} from the use lists for the given 53899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code oldSources} (rather than the sources currently 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * returned by insn.getSources()). 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 54199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn in question 542d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param oldSources {@code null-ok;} registers whose use lists 543d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * {@code insn} should be removed form 544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void removeFromUseList(SsaInsn insn, RegisterSpecList oldSources) { 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldSources == null) { 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 54941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szNew = oldSources.size(); 55141aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int i = 0; i < szNew; i++) { 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!useList[oldSources.get(i).getReg()].remove(insn)) { 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("use not found"); 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds an insn to both the use and def lists. For use when adding 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a new insn to the method. 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 56299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn to add 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 564d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /*package*/ void onInsnAdded(SsaInsn insn) { 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project onSourcesChanged(insn, null); 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project updateOneDefinition(insn, null); 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 570d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Removes an instruction from use and def lists. For use during 571d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * instruction removal. 572d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 573d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param insn {@code non-null;} insn to remove 574d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein */ 575d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /*package*/ void onInsnRemoved(SsaInsn insn) { 576d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein if (useList != null) { 577d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein removeFromUseList(insn, insn.getSources()); 578d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein } 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 580d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein RegisterSpec resultReg = insn.getResult(); 581d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein if (definitionList != null && resultReg != null) { 582d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein definitionList[resultReg.getReg()] = null; 583d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein } 584d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein } 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Indicates that the instruction list has changed or the SSA register 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * count has increased, so that internal datastructures that rely on 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it should be rebuild. In general, the various other on* methods 590d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * should be called in preference when changes occur if they are 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * applicable. 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void onInsnsChanged() { 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Definition list will need to be recomputed 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList = null; 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Use list will need to be recomputed 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList = null; 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unmodifiableUseList = null; 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Updates a single definition. 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 60599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} insn who's result should be recorded as 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a definition 607d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param oldResult {@code null-ok;} a previous result that should 608d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * be no longer considered a definition by this insn 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 610d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein /*package*/ void updateOneDefinition(SsaInsn insn, 611d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein RegisterSpec oldResult) { 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (definitionList == null) return; 613d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldResult != null) { 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = oldResult.getReg(); 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList[reg] = null; 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec resultReg = insn.getResult(); 620d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (resultReg != null) { 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = resultReg.getReg(); 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (definitionList[reg] != null) { 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("Duplicate add of insn"); 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList[resultReg.getReg()] = insn; 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 633d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Returns the list of all source uses (not results) for a register. 634d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param reg register in question 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return unmodifiable instruction list 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public List<SsaInsn> getUseListForRegister(int reg) { 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (unmodifiableUseList == null) { 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project buildUseList(); 642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return unmodifiableUseList[reg]; 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a modifiable copy of the register use list. 649d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return modifiable copy of the use-list, indexed by register 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public ArrayList<SsaInsn>[] getUseListCopy() { 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (useList == null) { 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project buildUseList(); 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn>[] useListCopy 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = (ArrayList<SsaInsn>[])(new ArrayList[registerCount]); 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < registerCount; i++) { 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useListCopy[i] = (ArrayList<SsaInsn>)(new ArrayList(useList[i])); 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return useListCopy; 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if the given SSA reg is ever associated with a local 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * local variable. Each SSA reg may be associated with at most one 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * local var. 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 67299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param spec {@code non-null;} ssa reg 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if reg is ever associated with a local 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean isRegALocal(RegisterSpec spec) { 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn defn = getDefinitionForRegister(spec.getReg()); 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (defn == null) { 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // version 0 registers are never used as locals 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Does the definition have a local associated with it? 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (defn.getLocalAssignment() != null) return true; 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // If not, is there a mark-local insn? 68741aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaInsn use : getUseListForRegister(spec.getReg())) { 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = use.getOriginalRopInsn(); 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn != null 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && insn.getOpcode().getOpcode() == RegOps.MARK_LOCAL) { 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 695d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the new register count after renaming. 701d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newRegCount new register count 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /*package*/ void setNewRegCount(int newRegCount) { 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project registerCount = newRegCount; 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project spareRegisterBase = registerCount; 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project onInsnsChanged(); 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Makes a new SSA register. For use after renaming has completed. 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 71399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >=0;} new SSA register. 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int makeNewSsaReg() { 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = registerCount++; 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project spareRegisterBase = registerCount; 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project onInsnsChanged(); 719d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein return reg; 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 723d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Visits all insns in this method. 724d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 72599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param visitor {@code non-null;} callback interface 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachInsn(SsaInsn.Visitor visitor) { 72841aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaBasicBlock block : blocks) { 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project block.forEachInsn(visitor); 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Visits each phi insn in this method 735d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param v {@code non-null;} callback. 736d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachPhiInsn(PhiInsn.Visitor v) { 73941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaBasicBlock block : blocks) { 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project block.forEachPhiInsn(v); 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 746d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Walks the basic block tree in depth-first order, calling the visitor 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method once for every block. This depth-first walk may be run forward 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * from the method entry point or backwards from the method exit points. 749d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param reverse true if this should walk backwards from the exit points 751d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * @param v {@code non-null;} callback interface. {@code parent} is set 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unless this is the root node 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachBlockDepthFirst(boolean reverse, 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock.Visitor v) { 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet visited = new BitSet(blocks.size()); 757d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein 758d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein // We push the parent first, then the child on the stack. 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>(); 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock rootBlock = reverse ? getExitBlock() : getEntryBlock(); 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (rootBlock == null) { 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // in the case there's no exit block 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 768d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein stack.add(null); // Start with null parent. 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.add(rootBlock); 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (stack.size() > 0) { 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock cur = stack.pop(); 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock parent = stack.pop(); 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!visited.get(cur.getIndex())) { 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet children 777d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein = reverse ? cur.getPredecessors() : cur.getSuccessors(); 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = children.nextSetBit(0); i >= 0 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; i = children.nextSetBit(i + 1)) { 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.add(cur); 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.add(blocks.get(i)); 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visited.set(cur.getIndex()); 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v.visitBlock(cur, parent); 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Visits blocks in dom-tree order, starting at the current node. 79199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * The {@code parent} parameter of the Visitor.visitBlock callback 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is currently always set to null. 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 79499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param v {@code non-null;} callback interface 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachBlockDepthFirstDom(SsaBasicBlock.Visitor v) { 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet visited = new BitSet(getBlocks().size()); 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>(); 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.add(getEntryBlock()); 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (stack.size() > 0) { 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock cur = stack.pop(); 804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaBasicBlock> curDomChildren = cur.getDomChildren(); 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!visited.get(cur.getIndex())) { 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We walk the tree this way for historical reasons... 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = curDomChildren.size() - 1; i >= 0; i--) { 809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock child = curDomChildren.get(i); 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stack.add(child); 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visited.set(cur.getIndex()); 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v.visitBlock(cur, null); 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 819d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Deletes all insns in the set from this method. 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 82199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param deletedInsns {@code non-null;} insns to delete 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void deleteInsns(Set<SsaInsn> deletedInsns) { 82441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaBasicBlock block : getBlocks()) { 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaInsn> insns = block.getInsns(); 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = insns.size() - 1; i >= 0; i--) { 828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = insns.get(i); 829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (deletedInsns.contains(insn)) { 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project onInsnRemoved(insn); 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.remove(i); 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Check to see if we need to add a GOTO 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int insnsSz = insns.size(); 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn lastInsn = (insnsSz == 0) ? null : insns.get(insnsSz - 1); 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block != getExitBlock() && (insnsSz == 0 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || lastInsn.getOriginalRopInsn() == null 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || lastInsn.getOriginalRopInsn().getOpcode() 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .getBranchingness() == Rop.BRANCH_NONE)) { 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // We managed to eat a throwable insn 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn gotoInsn = new PlainInsn(Rops.GOTO, 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition.NO_INFO, null, RegisterSpecList.EMPTY); 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(SsaInsn.makeFromRop(gotoInsn, block)); 850e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 851e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao // Remove secondary successors from this block 852e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao BitSet succs = block.getSuccessors(); 853e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (int i = succs.nextSetBit(0); i >= 0; 854e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao i = succs.nextSetBit(i + 1)) { 855e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (i != block.getPrimarySuccessorIndex()) { 856e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao block.removeSuccessor(i); 857e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 858e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 861f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 862f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 864d3190a0566518c28656cf5e6f41a8e8697775e26Dan Bornstein * Sets "back-convert mode". Set during back-conversion when registers 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are about to be mapped into a non-SSA namespace. When true, 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * use and def lists are unavailable. 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void setBackMode() { 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project backMode = true; 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project useList = null; 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project definitionList = null; 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 874