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.BasicBlock; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.BasicBlockList; 21e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Insn; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.InsnList; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.PlainInsn; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecList; 26e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.rop.code.Rop; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RopMethod; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Rops; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.SourcePosition; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Hex; 31e31ed7e916d212840dd5639afa01938bea58b2b8jeffhaoimport com.android.dx.util.IntList; 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntSet; 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Collections; 3699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Projectimport java.util.Comparator; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.List; 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * An SSA representation of a basic block. 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class SsaBasicBlock { 4399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 4499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code non-null;} comparator for instances of this class that 4599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * just compares block labels 4699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public static final Comparator<SsaBasicBlock> LABEL_COMPARATOR = 4899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project new LabelComparator(); 4964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 5099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} insn list associated with this instance */ 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ArrayList<SsaInsn> insns; 5299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 5399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} predecessor set (by block list index) */ 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet predecessors; 5599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 5699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} successor set (by block list index) */ 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet successors; 5899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 6099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code non-null;} ordered successor list 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (same block may be listed more than once) 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private IntList successorList; 6499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 6599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 6699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * block list index of primary successor, or {@code -1} for no primary 6799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * successor 6899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int primarySuccessor = -1; 7099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label of block in rop form */ 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int ropLabel; 7399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 7499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} method we belong to */ 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private SsaMethod parent; 7699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** our index into parent.getBlock() */ 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int index; 7999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of dom children */ 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<SsaBasicBlock> domChildren; 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** 8464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the number of moves added to the end of the block during the 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * phi-removal process. Retained for subsequent move scheduling. 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int movesFromPhisAtEnd = 0; 8899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 8964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /** 9064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * the number of moves added to the beginning of the block during the 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * phi-removal process. Retained for subsequent move scheduling. 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int movesFromPhisAtBeginning = 0; 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 96e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * contains last computed value of reachability of this block, or -1 97e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * if reachability hasn't been calculated yet 98e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 99e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao private int reachable = -1; 100e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 101e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 10299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code null-ok;} indexed by reg: the regs that are live-in at 10399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * this block 10499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private IntSet liveIn; 10699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 10799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 10899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code null-ok;} indexed by reg: the regs that are live-out at 10999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * this block 11099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private IntSet liveOut; 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 11499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Creates a new empty basic block. 11564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param basicBlockIndex index this block will have 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param ropLabel original rop-form label 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param parent method of this block 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock(final int basicBlockIndex, final int ropLabel, 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final SsaMethod parent) { 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.parent = parent; 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.index = basicBlockIndex; 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.insns = new ArrayList<SsaInsn>(); 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.ropLabel = ropLabel; 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.predecessors = new BitSet(parent.getBlocks().size()); 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.successors = new BitSet(parent.getBlocks().size()); 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.successorList = new IntList(); 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project domChildren = new ArrayList<SsaBasicBlock>(); 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Creates a new SSA basic block from a ROP form basic block. 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param rmeth original method 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param basicBlockIndex index this block will have 13964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param parent method of this block predecessor set will be 14064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * updated 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return new instance 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static SsaBasicBlock newFromRop(RopMethod rmeth, 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int basicBlockIndex, final SsaMethod parent) { 14599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project BasicBlockList ropBlocks = rmeth.getBlocks(); 14699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project BasicBlock bb = ropBlocks.get(basicBlockIndex); 14799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project SsaBasicBlock result = 14899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent); 14999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project InsnList ropInsns = bb.getInsns(); 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.insns.ensureCapacity(ropInsns.size()); 15299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0, sz = ropInsns.size() ; i < sz ; i++) { 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.insns.add(new NormalSsaInsn (ropInsns.get(i), result)); 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.predecessors = SsaMethod.bitSetFromLabelList( 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropBlocks, 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rmeth.labelToPredecessors(bb.getLabel())); 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.successors 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = SsaMethod.bitSetFromLabelList(ropBlocks, bb.getSuccessors()); 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.successorList 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = SsaMethod.indexListFromLabelList(ropBlocks, 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb.getSuccessors()); 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result.successorList.size() != 0) { 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccessor = bb.getPrimarySuccessor(); 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.primarySuccessor = (primarySuccessor < 0) 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ? -1 : ropBlocks.indexOfLabel(primarySuccessor); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a basic block as a dom child for this block. Used when constructing 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the dom tree. 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 18299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param child {@code non-null;} new dom child 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 18464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein public void addDomChild(SsaBasicBlock child) { 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project domChildren.add(child); 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the dom children for this node. Don't modify this list. 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 19199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} list of dom children 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 19364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein public ArrayList<SsaBasicBlock> getDomChildren() { 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return domChildren; 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a phi insn to the beginning of this block. The result type of 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the phi will be set to void, to indicate that it's currently unknown. 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 20199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param reg {@code >=0;} result reg 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 20364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein public void addPhiInsnForReg(int reg) { 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(0, new PhiInsn(reg, this)); 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a phi insn to the beginning of this block. This is to be used 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * when the result type or local-association can be determined at phi 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * insert time. 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 21299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param resultSpec {@code non-null;} reg 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 21464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein public void addPhiInsnForReg(RegisterSpec resultSpec) { 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(0, new PhiInsn(resultSpec, this)); 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds an insn to the head of this basic block, just after any phi 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * insns. 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 22299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} rop-form insn to add 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 22464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein public void addInsnToHead(Insn insn) { 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(getCountPhiInsns(), newInsn); 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.onInsnAdded(newInsn); 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replaces the last insn in this block. The provided insn must have 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * some branchingness. 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 23499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} rop-form insn to add, which must branch. 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 23664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein public void replaceLastInsn(Insn insn) { 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode().getBranchingness() == Rop.BRANCH_NONE) { 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("last insn must branch"); 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn oldInsn = insns.get(insns.size() - 1); 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(insns.size() - 1, newInsn); 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.onInsnRemoved(oldInsn); 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.onInsnAdded(newInsn); 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 25199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Visits each phi insn. 25264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 25399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param v {@code non-null;} the callback 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachPhiInsn(PhiInsn.Visitor v) { 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = insns.size(); 25764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = insns.get(i); 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof PhiInsn) { 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v.visitPhiInsn((PhiInsn) insn); 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Presently we assume PhiInsn's are in a continuous 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block at the top of the list 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Deletes all phi insns. Do this after adding appropriate move insns. 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void removeAllPhiInsns() { 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Presently we assume PhiInsn's are in a continuous 27864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * block at the top of the list. 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.subList(0, getCountPhiInsns()).clear(); 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the number of phi insns at the top of this basic block. 28664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return count of phi insns 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getCountPhiInsns() { 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int countPhiInsns; 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = insns.size(); 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) { 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = insns.get(countPhiInsns); 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!(insn instanceof PhiInsn)) { 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return countPhiInsns; 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 30499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the (mutable) instruction list for this block, 30564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * with phi insns at the beginning 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public ArrayList<SsaInsn> getInsns() { 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return insns; 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 31299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the (mutable) list of phi insns for this block 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public List<SsaInsn> getPhiInsns() { 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return insns.subList(0, getCountPhiInsns()); 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the block index of this block 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getIndex() { 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return index; 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the label of this block in rop form 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getRopLabel() { 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ropLabel; 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the label of this block in rop form as a hex string 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public String getRopLabelString() { 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return Hex.u2(ropLabel); 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 34099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} predecessors set, indexed by block index 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BitSet getPredecessors() { 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return predecessors; 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 34799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} successors set, indexed by block index 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BitSet getSuccessors() { 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return successors; 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 35499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} ordered successor list, containing block 35599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * indicies 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList getSuccessorList() { 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return successorList; 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 36299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= -1;} block index of primary successor or 36364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * {@code -1} if no primary successor 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getPrimarySuccessorIndex() { 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return primarySuccessor; 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return rop label of primary successor 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getPrimarySuccessorRopLabel() { 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return parent.blockIndexToRopLabel(primarySuccessor); 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 37799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} the primary successor block or {@code null} 37899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * if there is none 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock getPrimarySuccessor() { 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySuccessor < 0) { 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return parent.getBlocks().get(primarySuccessor); 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return successor list of rop labels 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList getRopLabelSuccessorList() { 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList result = new IntList(successorList.size()); 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = successorList.size(); 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(parent.blockIndexToRopLabel(successorList.get(i))); 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 40399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} method that contains this block 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaMethod getParent() { 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return parent; 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inserts a new empty GOTO block as a predecessor to this block. 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * All previous predecessors will be predecessors to the new block. 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 41399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} an appropriately-constructed instance 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock insertNewPredecessor() { 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock newPred = parent.makeNewGotoBlock(); 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Update the new block. 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPred.predecessors = predecessors; 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPred.successors.set(index) ; 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPred.successorList.add(index); 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPred.primarySuccessor = index; 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 42564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Update us. 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project predecessors = new BitSet(parent.getBlocks().size()); 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project predecessors.set(newPred.index); 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 42964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Update our (soon-to-be) old predecessors. 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = newPred.predecessors.nextSetBit(0); i >= 0; 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i = newPred.predecessors.nextSetBit(i + 1)) { 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock predBlock = parent.getBlocks().get(i); 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project predBlock.replaceSuccessor(index, newPred.index); 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newPred; 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 44299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs and inserts a new empty GOTO block {@code Z} between 44399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * this block ({@code A}) and a current successor block 44499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * ({@code B}). The new block will replace B as A's successor and 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A as B's predecessor. A and B will no longer be directly connected. 446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If B is listed as a successor multiple times, all references 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are replaced. 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param other current successor (B) 45099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} an appropriately-constructed instance 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other) { 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock newSucc = parent.makeNewGotoBlock(); 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!successors.get(other.index)) { 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("Block " + other.getRopLabelString() 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + " not successor of " + getRopLabelString()); 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 46064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Update the new block. 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.predecessors.set(this.index); 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.successors.set(other.index) ; 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.successorList.add(other.index); 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.primarySuccessor = other.index; 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 46664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Update us. 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = successorList.size() - 1 ; i >= 0; i--) { 46841aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein if (successorList.get(i) == other.index) { 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successorList.set(i, newSucc.index); 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySuccessor == other.index) { 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = newSucc.index; 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.clear(other.index); 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.set(newSucc.index); 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 47964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // Update "other". 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project other.predecessors.set(newSucc.index); 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project other.predecessors.set(index, successors.get(other.index)); 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newSucc; 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 48799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Replaces an old successor with a new successor. This will throw 48899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * RuntimeException if {@code oldIndex} was not a successor. 48964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldIndex index of old successor block 49164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @param newIndex index of new successor block 492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void replaceSuccessor(int oldIndex, int newIndex) { 494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldIndex == newIndex) { 495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 49899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Update us. 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.set(newIndex); 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySuccessor == oldIndex) { 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = newIndex; 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = successorList.size() - 1 ; i >= 0; i--) { 50641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein if (successorList.get(i) == oldIndex) { 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successorList.set(i, newIndex); 508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.clear(oldIndex); 512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 51399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Update new successor. 514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.getBlocks().get(newIndex).predecessors.set(index); 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 51699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Update old successor. 517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.getBlocks().get(oldIndex).predecessors.clear(index); 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 520e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 521e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Removes a successor from this block's successor list. 522e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 523e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param oldIndex index of successor block to remove 524e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 525e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void removeSuccessor(int oldIndex) { 526e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao int removeIndex = 0; 527e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 528e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao for (int i = successorList.size() - 1; i >= 0; i--) { 529e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (successorList.get(i) == oldIndex) { 530e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao removeIndex = i; 531e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } else { 532e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao primarySuccessor = successorList.get(i); 533e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 534e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 535e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 536e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao successorList.removeIndex(removeIndex); 537e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao successors.clear(oldIndex); 538e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao parent.getBlocks().get(oldIndex).predecessors.clear(index); 539e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attaches block to an exit block if necessary. If this block 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is not an exit predecessor or is the exit block, this block does 544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * nothing. For use by {@link com.android.dx.ssa.SsaMethod#makeExitBlock} 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 54699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param exitBlock {@code non-null;} exit block 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void exitBlockFixup(SsaBasicBlock exitBlock) { 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (this == exitBlock) { 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (successorList.size() == 0) { 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This is an exit predecessor. 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Set the successor to the exit block 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.set(exitBlock.index); 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successorList.add(exitBlock.index); 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = exitBlock.index; 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exitBlock.predecessors.set(this.index); 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a move instruction to the end of this basic block, just 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * before the last instruction. If the result of the final instruction 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is the source in question, then the move is placed at the beginning of 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the primary successor block. This is for unversioned registers. 57064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param result move destination 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param source move source 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void addMoveToEnd(RegisterSpec result, RegisterSpec source) { 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result.getReg() == source.getReg()) { 577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Sometimes we end up with no-op moves. Ignore them here. 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The last Insn has to be a normal SSA insn: a phi can't branch 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * or return or cause an exception, etc. 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project NormalSsaInsn lastInsn; 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastInsn = (NormalSsaInsn)insns.get(insns.size()-1); 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) { 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 59064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * The final insn in this block has a source or result 59164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * register, and the moves we may need to place and 59264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * schedule may interfere. We need to insert this 59364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * instruction at the beginning of the primary successor 59464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * block instead. We know this is safe, because when we 59564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * edge-split earlier, we ensured that each successor has 59664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * only us as a predecessor. 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = successors.nextSetBit(0) 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; i >= 0 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; i = successors.nextSetBit(i + 1)) { 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock succ; 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succ = parent.getBlocks().get(i); 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succ.addMoveToBeginning(result, source); 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 61064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * We can safely add a move to the end of the block just 61164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * before the last instruction, because the final insn does 61264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * not assign to anything. 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 61464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein RegisterSpecList sources = RegisterSpecList.make(source); 61564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein NormalSsaInsn toAdd = new NormalSsaInsn( 61699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project new PlainInsn(Rops.opMove(result.getType()), 61799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project SourcePosition.NO_INFO, result, sources), this); 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(insns.size() - 1, toAdd); 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project movesFromPhisAtEnd++; 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 62699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Adds a move instruction after the phi insn block. 62764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param result move destination 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param source move source 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void addMoveToBeginning (RegisterSpec result, RegisterSpec source) { 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result.getReg() == source.getReg()) { 633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Sometimes we end up with no-op moves. Ignore them here. 634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 63764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein RegisterSpecList sources = RegisterSpecList.make(source); 63864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein NormalSsaInsn toAdd = new NormalSsaInsn( 63964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein new PlainInsn(Rops.opMove(result.getType()), 64064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein SourcePosition.NO_INFO, result, sources), this); 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(getCountPhiInsns(), toAdd); 64364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein movesFromPhisAtBeginning++; 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the register as used in a bitset, taking into account its 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * category/width. 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param regsUsed set, indexed by register number 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param rs register to mark as used 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void setRegsUsed (BitSet regsUsed, RegisterSpec rs) { 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regsUsed.set(rs.getReg()); 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (rs.getCategory() > 1) { 65664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein regsUsed.set(rs.getReg() + 1); 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if the register is used in a bitset, taking 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * into account its category/width. 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param regsUsed set, indexed by register number 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param rs register to mark as used 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if register is fully or partially (for the case of wide 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers) used. 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean checkRegUsed (BitSet regsUsed, RegisterSpec rs) { 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = rs.getReg(); 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int category = rs.getCategory(); 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return regsUsed.get(reg) 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || (category == 2 ? regsUsed.get(reg + 1) : false); 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Ensures that all move operations in this block occur such that 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * reads of any register happen before writes to that register. 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * NOTE: caller is expected to returnSpareRegisters()! 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 68299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * TODO: See Briggs, et al "Practical Improvements to the Construction and 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Destruction of Static Single Assignment Form" section 5. a) This can 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be done in three passes. 68564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param toSchedule List of instructions. Must consist only of moves. 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule) { 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet regsUsedAsSources = new BitSet(parent.getRegCount()); 69064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 69164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // TODO: Get rid of this. 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet regsUsedAsResults = new BitSet(parent.getRegCount()); 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = toSchedule.size(); 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int insertPlace = 0; 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (insertPlace < sz) { 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int oldInsertPlace = insertPlace; 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Record all registers used as sources in this block. 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = insertPlace; i < sz; i++) { 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setRegsUsed(regsUsedAsSources, 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toSchedule.get(i).getSources().get(0)); 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setRegsUsed(regsUsedAsResults, 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toSchedule.get(i).getResult()); 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If there are no circular dependencies, then there exists 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * n instructions where n > 1 whose result is not used as a source. 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = insertPlace; i <sz; i++) { 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = toSchedule.get(i); 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Move these n registers to the front, since they overwrite 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * nothing. 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!checkRegUsed(regsUsedAsSources, insn.getResult())) { 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Collections.swap(toSchedule, i, insertPlace++); 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 72664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 72764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * If we've made no progress in this iteration, there's a 72864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * circular dependency. Split it using the temp reg. 72964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldInsertPlace == insertPlace) { 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insnToSplit = null; 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Find an insn whose result is used as a source. 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = insertPlace; i < sz; i++) { 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn insn = toSchedule.get(i); 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (checkRegUsed(regsUsedAsSources, insn.getResult()) 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && checkRegUsed(regsUsedAsResults, 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.getSources().get(0))) { 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insnToSplit = insn; 74264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 74364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * We're going to split this insn; move it to the 74464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * front. 74564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Collections.swap(toSchedule, insertPlace, i); 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // At least one insn will be set above. 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = insnToSplit.getResult(); 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec tempSpec = result.withReg( 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.borrowSpareRegister(result.getCategory())); 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein NormalSsaInsn toAdd = new NormalSsaInsn( 75864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein new PlainInsn(Rops.opMove(result.getType()), 75964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein SourcePosition.NO_INFO, 76064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein tempSpec, 76164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein insnToSplit.getSources()), this); 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toSchedule.add(insertPlace++, toAdd); 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein RegisterSpecList newSources = RegisterSpecList.make(tempSpec); 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein NormalSsaInsn toReplace = new NormalSsaInsn( 76864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein new PlainInsn(Rops.opMove(result.getType()), 76964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein SourcePosition.NO_INFO, 77064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein result, 77164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein newSources), this); 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toSchedule.set(insertPlace, toReplace); 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 77564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // The size changed. 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sz = toSchedule.size(); 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regsUsedAsSources.clear(); 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regsUsedAsResults.clear(); 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 78599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Adds {@code regV} to the live-out list for this block. This is called 78699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * by the liveness analyzer. 78764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param regV register that is live-out for this block. 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 79099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public void addLiveOut (int regV) { 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (liveOut == null) { 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project liveOut.add(regV); 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 79999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Adds {@code regV} to the live-in list for this block. This is 80099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * called by the liveness analyzer. 80164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param regV register that is live-in for this block. 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 80499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public void addLiveIn (int regV) { 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (liveIn == null) { 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 80964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein liveIn.add(regV); 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the set of live-in registers. Valid after register 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interference graph has been generated, otherwise empty. 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 81699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} live-in register set. 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntSet getLiveInRegs() { 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (liveIn == null) { 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return liveIn; 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the set of live-out registers. Valid after register 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interference graph has been generated, otherwise empty. 82864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 82964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code non-null;} live-out register set 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntSet getLiveOutRegs() { 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (liveOut == null) { 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return liveOut; 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if this is the one-and-only exit block for this method 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean isExitBlock() { 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return index == parent.getExitBlockIndex(); 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 846e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Returns true if this block was last calculated to be reachable. 847e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Recalculates reachability if value has never been computed. 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 84964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * @return {@code true} if reachable 850f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean isReachable() { 852e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao if (reachable == -1) { 853e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao parent.computeReachability(); 854e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 855e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao return (reachable == 1); 856e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao } 857e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao 858e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao /** 859e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * Sets reachability of block to specified value 860e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * 861e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao * @param reach new value of reachability for block 862e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao */ 863e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao public void setReachable(int reach) { 864e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao reachable = reach; 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 86664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 86899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Sorts move instructions added via {@code addMoveToEnd} during 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * phi removal so that results don't overwrite sources that are used. 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * For use after all phis have been removed and all calls to 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * addMoveToEnd() have been made.<p> 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This is necessary because copy-propogation may have left us in a state 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * where the same basic block has the same register as a phi operand 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and a result. In this case, the register in the phi operand always 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * refers value before any other phis have executed. 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 878f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void scheduleMovesFromPhis() { 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (movesFromPhisAtBeginning > 1) { 880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project List<SsaInsn> toSchedule; 881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toSchedule = insns.subList(0, movesFromPhisAtBeginning); 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project scheduleUseBeforeAssigned(toSchedule); 885f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning); 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 88864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 88964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * TODO: It's actually possible that this case never happens, 89064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * because a move-exception block, having only one predecessor 89164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * in SSA form, perhaps is never on a dominance frontier. 89264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (firstNonPhiMoveInsn.isMoveException()) { 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (true) { 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We've yet to observe this case, and if it can 89764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * occur the code written to handle it probably 898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * does not work. 899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException( 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "Unexpected: moves from " 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project +"phis before move-exception"); 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 90464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 90564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * A move-exception insn must be placed first in this block 90664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * We need to move it there, and deal with possible 90764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * interference. 90864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean moveExceptionInterferes = false; 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int moveExceptionResult 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = firstNonPhiMoveInsn.getResult().getReg(); 913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 91464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 91564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Does the move-exception result reg interfere with the 91664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * phi moves? 91764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 91841aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (SsaInsn insn : toSchedule) { 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.isResultReg(moveExceptionResult) 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project || insn.isRegASource(moveExceptionResult)) { 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project moveExceptionInterferes = true; 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!moveExceptionInterferes) { 92799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // This is the easy case. 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.remove(movesFromPhisAtBeginning); 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(0, firstNonPhiMoveInsn); 930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 93164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 93264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * We need to move the result to a spare reg 93364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * and move it back. 93464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 93564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein RegisterSpec originalResultSpec 93664986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein = firstNonPhiMoveInsn.getResult(); 93764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein int spareRegister = parent.borrowSpareRegister( 938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project originalResultSpec.getCategory()); 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // We now move it to a spare register. 941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project firstNonPhiMoveInsn.changeResultReg(spareRegister); 94299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project RegisterSpec tempSpec = 94399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project firstNonPhiMoveInsn.getResult(); 944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(0, firstNonPhiMoveInsn); 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein // And here we move it back. 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein NormalSsaInsn toAdd = new NormalSsaInsn( 95064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein new PlainInsn( 95164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein Rops.opMove(tempSpec.getType()), 95264986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein SourcePosition.NO_INFO, 95364986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein originalResultSpec, 95464986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein RegisterSpecList.make(tempSpec)), 955f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this); 956f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 957f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95864986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein /* 95964986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Place it immediately after the phi-moves, 96064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * overwriting the move-exception that was there. 96164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein */ 962f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(movesFromPhisAtBeginning + 1, toAdd); 963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 964f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 965f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 96764986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein 968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (movesFromPhisAtEnd > 1) { 969f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project scheduleUseBeforeAssigned( 970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.subList(insns.size() - movesFromPhisAtEnd - 1, 971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.size() - 1)); 972f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 97499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Return registers borrowed here and in scheduleUseBeforeAssigned(). 975f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project parent.returnSpareRegisters(); 976f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 977f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 978f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 979f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 98064986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * Visits all insns in this block. 98164986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 98299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param visitor {@code non-null;} callback interface 983f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachInsn(SsaInsn.Visitor visitor) { 98543c5658262370beac0b13286d6d7d1b330113e62Marco Nelissen // This gets called a LOT, and not using an iterator 98643c5658262370beac0b13286d6d7d1b330113e62Marco Nelissen // saves a lot of allocations and reduces memory usage 98743c5658262370beac0b13286d6d7d1b330113e62Marco Nelissen int len = insns.size(); 98843c5658262370beac0b13286d6d7d1b330113e62Marco Nelissen for (int i = 0; i < len; i++) { 98943c5658262370beac0b13286d6d7d1b330113e62Marco Nelissen insns.get(i).accept(visitor); 990f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 991f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 992f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 99399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@inheritDoc} */ 994e31ed7e916d212840dd5639afa01938bea58b2b8jeffhao @Override 995f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public String toString() { 996f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return "{" + index + ":" + Hex.u2(ropLabel) + '}'; 997f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 998f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 999f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 100099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Visitor interface for basic blocks. 1001f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1002f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public interface Visitor { 1003f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1004f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Indicates a block has been visited by an iterator method. 100564986d4f1b50a5f3a12e05eb179ae9ad555814e7Dan Bornstein * 100699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param v {@code non-null;} block visited 100799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param parent {@code null-ok;} parent node if applicable 1008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void visitBlock (SsaBasicBlock v, SsaBasicBlock parent); 1010f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 101199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 101299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 101399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Label comparator. 101499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 101599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public static final class LabelComparator 101699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project implements Comparator<SsaBasicBlock> { 101799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@inheritDoc} */ 101899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public int compare(SsaBasicBlock b1, SsaBasicBlock b2) { 101999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project int label1 = b1.ropLabel; 102099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project int label2 = b2.ropLabel; 102199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 102299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (label1 < label2) { 102399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project return -1; 102499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } else if (label1 > label2) { 102599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project return 1; 102699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } else { 102799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project return 0; 102899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 102999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 103099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 1031f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 1032