1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.ssa; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.BasicBlock; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.BasicBlockList; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Insn; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.InsnList; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.PlainInsn; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rop; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RopMethod; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rops; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.SourcePosition; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.Hex; 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntSet; 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.Collections; 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.Comparator; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.List; 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * An SSA representation of a basic block. 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class SsaBasicBlock { 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code non-null;} comparator for instances of this class that 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * just compares block labels 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static final Comparator<SsaBasicBlock> LABEL_COMPARATOR = 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new LabelComparator(); 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} insn list associated with this instance */ 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private ArrayList<SsaInsn> insns; 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} predecessor set (by block list index) */ 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private BitSet predecessors; 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} successor set (by block list index) */ 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private BitSet successors; 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code non-null;} ordered successor list 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * (same block may be listed more than once) 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private IntList successorList; 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block list index of primary successor, or {@code -1} for no primary 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * successor 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int primarySuccessor = -1; 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** label of block in rop form */ 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int ropLabel; 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} method we belong to */ 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private SsaMethod parent; 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** our index into parent.getBlock() */ 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int index; 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** list of dom children */ 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaBasicBlock> domChildren; 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the number of moves added to the end of the block during the 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * phi-removal process. Retained for subsequent move scheduling. 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int movesFromPhisAtEnd = 0; 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the number of moves added to the beginning of the block during the 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * phi-removal process. Retained for subsequent move scheduling. 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int movesFromPhisAtBeginning = 0; 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * contains last computed value of reachability of this block, or -1 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * if reachability hasn't been calculated yet 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int reachable = -1; 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code null-ok;} indexed by reg: the regs that are live-in at 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * this block 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private IntSet liveIn; 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code null-ok;} indexed by reg: the regs that are live-out at 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * this block 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private IntSet liveOut; 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Creates a new empty basic block. 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param basicBlockIndex index this block will have 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ropLabel original rop-form label 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param parent method of this block 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock(final int basicBlockIndex, final int ropLabel, 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson final SsaMethod parent) { 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.parent = parent; 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.index = basicBlockIndex; 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.insns = new ArrayList<SsaInsn>(); 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.ropLabel = ropLabel; 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.predecessors = new BitSet(parent.getBlocks().size()); 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.successors = new BitSet(parent.getBlocks().size()); 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.successorList = new IntList(); 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domChildren = new ArrayList<SsaBasicBlock>(); 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Creates a new SSA basic block from a ROP form basic block. 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rmeth original method 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param basicBlockIndex index this block will have 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param parent method of this block predecessor set will be 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * updated 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return new instance 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static SsaBasicBlock newFromRop(RopMethod rmeth, 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int basicBlockIndex, final SsaMethod parent) { 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlockList ropBlocks = rmeth.getBlocks(); 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock bb = ropBlocks.get(basicBlockIndex); 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock result = 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent); 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson InsnList ropInsns = bb.getInsns(); 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.insns.ensureCapacity(ropInsns.size()); 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0, sz = ropInsns.size() ; i < sz ; i++) { 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.insns.add(new NormalSsaInsn (ropInsns.get(i), result)); 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.predecessors = SsaMethod.bitSetFromLabelList( 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ropBlocks, 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson rmeth.labelToPredecessors(bb.getLabel())); 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.successors 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = SsaMethod.bitSetFromLabelList(ropBlocks, bb.getSuccessors()); 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.successorList 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = SsaMethod.indexListFromLabelList(ropBlocks, 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bb.getSuccessors()); 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result.successorList.size() != 0) { 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int primarySuccessor = bb.getPrimarySuccessor(); 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.primarySuccessor = (primarySuccessor < 0) 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ? -1 : ropBlocks.indexOfLabel(primarySuccessor); 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds a basic block as a dom child for this block. Used when constructing 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the dom tree. 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param child {@code non-null;} new dom child 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addDomChild(SsaBasicBlock child) { 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domChildren.add(child); 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the dom children for this node. Don't modify this list. 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} list of dom children 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public ArrayList<SsaBasicBlock> getDomChildren() { 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return domChildren; 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds a phi insn to the beginning of this block. The result type of 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the phi will be set to void, to indicate that it's currently unknown. 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reg {@code >=0;} result reg 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addPhiInsnForReg(int reg) { 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(0, new PhiInsn(reg, this)); 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds a phi insn to the beginning of this block. This is to be used 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * when the result type or local-association can be determined at phi 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * insert time. 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param resultSpec {@code non-null;} reg 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addPhiInsnForReg(RegisterSpec resultSpec) { 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(0, new PhiInsn(resultSpec, this)); 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds an insn to the head of this basic block, just after any phi 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * insns. 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} rop-form insn to add 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addInsnToHead(Insn insn) { 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(getCountPhiInsns(), newInsn); 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.onInsnAdded(newInsn); 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Replaces the last insn in this block. The provided insn must have 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * some branchingness. 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param insn {@code non-null;} rop-form insn to add, which must branch. 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void replaceLastInsn(Insn insn) { 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insn.getOpcode().getBranchingness() == Rop.BRANCH_NONE) { 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("last insn must branch"); 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn oldInsn = insns.get(insns.size() - 1); 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.set(insns.size() - 1, newInsn); 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.onInsnRemoved(oldInsn); 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.onInsnAdded(newInsn); 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Visits each phi insn. 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param v {@code non-null;} the callback 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void forEachPhiInsn(PhiInsn.Visitor v) { 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = insns.size(); 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = insns.get(i); 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insn instanceof PhiInsn) { 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson v.visitPhiInsn((PhiInsn) insn); 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Presently we assume PhiInsn's are in a continuous 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block at the top of the list 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 273579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 274579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Deletes all phi insns. Do this after adding appropriate move insns. 275579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 276579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void removeAllPhiInsns() { 277579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 278579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Presently we assume PhiInsn's are in a continuous 279579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block at the top of the list. 280579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 281579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 282579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.subList(0, getCountPhiInsns()).clear(); 283579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 284579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 285579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 286579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the number of phi insns at the top of this basic block. 287579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 288579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return count of phi insns 289579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 290579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int getCountPhiInsns() { 291579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int countPhiInsns; 292579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 293579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = insns.size(); 294579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) { 295579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = insns.get(countPhiInsns); 296579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!(insn instanceof PhiInsn)) { 297579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 298579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 299579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 300579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 301579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return countPhiInsns; 302579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 303579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 304579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 305579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the (mutable) instruction list for this block, 306579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * with phi insns at the beginning 307579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 308579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public ArrayList<SsaInsn> getInsns() { 309579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return insns; 310579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 311579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 312579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 313579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the (mutable) list of phi insns for this block 314579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 315579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public List<SsaInsn> getPhiInsns() { 316579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return insns.subList(0, getCountPhiInsns()); 317579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 318579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 319579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 320579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return the block index of this block 321579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 322579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int getIndex() { 323579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return index; 324579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 325579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 326579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 327579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return the label of this block in rop form 328579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 329579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int getRopLabel() { 330579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ropLabel; 331579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 332579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 333579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 334579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return the label of this block in rop form as a hex string 335579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 336579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public String getRopLabelString() { 337579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return Hex.u2(ropLabel); 338579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 339579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 340579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 341579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} predecessors set, indexed by block index 342579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 343579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public BitSet getPredecessors() { 344579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return predecessors; 345579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 346579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 347579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 348579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} successors set, indexed by block index 349579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 350579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public BitSet getSuccessors() { 351579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return successors; 352579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 353579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 354579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 355579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} ordered successor list, containing block 356579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * indicies 357579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 358579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList getSuccessorList() { 359579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return successorList; 360579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 361579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 362579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 363579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code >= -1;} block index of primary successor or 364579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code -1} if no primary successor 365579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 366579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int getPrimarySuccessorIndex() { 367579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return primarySuccessor; 368579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 369579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 370579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 371579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return rop label of primary successor 372579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 373579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int getPrimarySuccessorRopLabel() { 374579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return parent.blockIndexToRopLabel(primarySuccessor); 375579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 376579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 377579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 378579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code null-ok;} the primary successor block or {@code null} 379579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * if there is none 380579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 381579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock getPrimarySuccessor() { 382579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (primarySuccessor < 0) { 383579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return null; 384579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 385579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return parent.getBlocks().get(primarySuccessor); 386579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 387579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 388579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 389579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 390579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return successor list of rop labels 391579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 392579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList getRopLabelSuccessorList() { 393579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList result = new IntList(successorList.size()); 394579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 395579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = successorList.size(); 396579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 397579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 398579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.add(parent.blockIndexToRopLabel(successorList.get(i))); 399579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 400579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 401579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 402579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 403579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 404579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} method that contains this block 405579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 406579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaMethod getParent() { 407579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return parent; 408579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 409579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 410579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 411579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts a new empty GOTO block as a predecessor to this block. 412579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * All previous predecessors will be predecessors to the new block. 413579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 414579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} an appropriately-constructed instance 415579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 416579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock insertNewPredecessor() { 417579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock newPred = parent.makeNewGotoBlock(); 418579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 419579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update the new block. 420579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newPred.predecessors = predecessors; 421579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newPred.successors.set(index) ; 422579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newPred.successorList.add(index); 423579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newPred.primarySuccessor = index; 424579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 425579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 426579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update us. 427579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson predecessors = new BitSet(parent.getBlocks().size()); 428579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson predecessors.set(newPred.index); 429579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 430579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update our (soon-to-be) old predecessors. 431579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = newPred.predecessors.nextSetBit(0); i >= 0; 432579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson i = newPred.predecessors.nextSetBit(i + 1)) { 433579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 434579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock predBlock = parent.getBlocks().get(i); 435579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 436579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson predBlock.replaceSuccessor(index, newPred.index); 437579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 438579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 439579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return newPred; 440579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 441579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 442579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 443579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs and inserts a new empty GOTO block {@code Z} between 444579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * this block ({@code A}) and a current successor block 445579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * ({@code B}). The new block will replace B as A's successor and 446579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A as B's predecessor. A and B will no longer be directly connected. 447579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If B is listed as a successor multiple times, all references 448579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * are replaced. 449579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 450579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param other current successor (B) 451579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} an appropriately-constructed instance 452579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 453579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other) { 454579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock newSucc = parent.makeNewGotoBlock(); 455579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 456579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!successors.get(other.index)) { 457579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException("Block " + other.getRopLabelString() 458579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + " not successor of " + getRopLabelString()); 459579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 460579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 461579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update the new block. 462579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSucc.predecessors.set(this.index); 463579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSucc.successors.set(other.index) ; 464579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSucc.successorList.add(other.index); 465579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSucc.primarySuccessor = other.index; 466579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 467579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update us. 468579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = successorList.size() - 1 ; i >= 0; i--) { 469579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (successorList.get(i) == other.index) { 470579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList.set(i, newSucc.index); 471579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 472579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 473579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 474579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (primarySuccessor == other.index) { 475579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primarySuccessor = newSucc.index; 476579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 477579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successors.clear(other.index); 478579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successors.set(newSucc.index); 479579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 480579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update "other". 481579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson other.predecessors.set(newSucc.index); 482579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson other.predecessors.set(index, successors.get(other.index)); 483579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 484579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return newSucc; 485579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 486579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 487579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 488579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Replaces an old successor with a new successor. This will throw 489579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * RuntimeException if {@code oldIndex} was not a successor. 490579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 491579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param oldIndex index of old successor block 492579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newIndex index of new successor block 493579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 494579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void replaceSuccessor(int oldIndex, int newIndex) { 495579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (oldIndex == newIndex) { 496579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return; 497579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 498579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 499579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update us. 500579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successors.set(newIndex); 501579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 502579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (primarySuccessor == oldIndex) { 503579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primarySuccessor = newIndex; 504579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 505579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 506579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = successorList.size() - 1 ; i >= 0; i--) { 507579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (successorList.get(i) == oldIndex) { 508579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList.set(i, newIndex); 509579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 510579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 511579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 512579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successors.clear(oldIndex); 513579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 514579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update new successor. 515579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.getBlocks().get(newIndex).predecessors.set(index); 516579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 517579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update old successor. 518579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.getBlocks().get(oldIndex).predecessors.clear(index); 519579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 520579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 521579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 522579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Removes a successor from this block's successor list. 523579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 524579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param oldIndex index of successor block to remove 525579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 526579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void removeSuccessor(int oldIndex) { 527579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int removeIndex = 0; 528579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 529579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = successorList.size() - 1; i >= 0; i--) { 530579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (successorList.get(i) == oldIndex) { 531579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson removeIndex = i; 532579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 533579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primarySuccessor = successorList.get(i); 534579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 535579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 536579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 537579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList.removeIndex(removeIndex); 538579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successors.clear(oldIndex); 539579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.getBlocks().get(oldIndex).predecessors.clear(index); 540579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 541579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 542579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 543579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Attaches block to an exit block if necessary. If this block 544579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * is not an exit predecessor or is the exit block, this block does 545579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * nothing. For use by {@link com.android.dx.ssa.SsaMethod#makeExitBlock} 546579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 547579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param exitBlock {@code non-null;} exit block 548579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 549579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void exitBlockFixup(SsaBasicBlock exitBlock) { 550579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (this == exitBlock) { 551579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return; 552579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 553579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 554579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (successorList.size() == 0) { 555579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 556579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This is an exit predecessor. 557579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Set the successor to the exit block 558579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 559579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successors.set(exitBlock.index); 560579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList.add(exitBlock.index); 561579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primarySuccessor = exitBlock.index; 562579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson exitBlock.predecessors.set(this.index); 563579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 564579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 565579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 566579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 567579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds a move instruction to the end of this basic block, just 568579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * before the last instruction. If the result of the final instruction 569579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * is the source in question, then the move is placed at the beginning of 570579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the primary successor block. This is for unversioned registers. 571579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 572579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param result move destination 573579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param source move source 574579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 575579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addMoveToEnd(RegisterSpec result, RegisterSpec source) { 576579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 577579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result.getReg() == source.getReg()) { 578579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Sometimes we end up with no-op moves. Ignore them here. 579579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return; 580579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 581579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 582579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 583579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The last Insn has to be a normal SSA insn: a phi can't branch 584579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * or return or cause an exception, etc. 585579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 586579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn lastInsn; 587579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson lastInsn = (NormalSsaInsn)insns.get(insns.size()-1); 588579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 589579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) { 590579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 591579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The final insn in this block has a source or result 592579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * register, and the moves we may need to place and 593579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * schedule may interfere. We need to insert this 594579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * instruction at the beginning of the primary successor 595579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block instead. We know this is safe, because when we 596579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * edge-split earlier, we ensured that each successor has 597579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * only us as a predecessor. 598579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 599579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 600579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = successors.nextSetBit(0) 601579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ; i >= 0 602579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ; i = successors.nextSetBit(i + 1)) { 603579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 604579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock succ; 605579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 606579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson succ = parent.getBlocks().get(i); 607579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson succ.addMoveToBeginning(result, source); 608579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 609579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 610579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 611579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We can safely add a move to the end of the block just 612579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * before the last instruction, because the final insn does 613579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * not assign to anything. 614579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 615579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = RegisterSpecList.make(source); 616579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn toAdd = new NormalSsaInsn( 617579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PlainInsn(Rops.opMove(result.getType()), 618579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SourcePosition.NO_INFO, result, sources), this); 619579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 620579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(insns.size() - 1, toAdd); 621579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 622579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson movesFromPhisAtEnd++; 623579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 624579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 625579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 626579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 627579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds a move instruction after the phi insn block. 628579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 629579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param result move destination 630579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param source move source 631579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 632579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addMoveToBeginning (RegisterSpec result, RegisterSpec source) { 633579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result.getReg() == source.getReg()) { 634579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Sometimes we end up with no-op moves. Ignore them here. 635579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return; 636579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 637579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 638579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = RegisterSpecList.make(source); 639579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn toAdd = new NormalSsaInsn( 640579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PlainInsn(Rops.opMove(result.getType()), 641579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SourcePosition.NO_INFO, result, sources), this); 642579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 643579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(getCountPhiInsns(), toAdd); 644579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson movesFromPhisAtBeginning++; 645579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 646579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 647579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 648579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Sets the register as used in a bitset, taking into account its 649579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * category/width. 650579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 651579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regsUsed set, indexed by register number 652579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rs register to mark as used 653579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 654579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static void setRegsUsed (BitSet regsUsed, RegisterSpec rs) { 655579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regsUsed.set(rs.getReg()); 656579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (rs.getCategory() > 1) { 657579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regsUsed.set(rs.getReg() + 1); 658579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 659579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 660579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 661579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 662579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Checks to see if the register is used in a bitset, taking 663579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * into account its category/width. 664579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 665579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regsUsed set, indexed by register number 666579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rs register to mark as used 667579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return true if register is fully or partially (for the case of wide 668579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * registers) used. 669579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 670579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean checkRegUsed (BitSet regsUsed, RegisterSpec rs) { 671579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int reg = rs.getReg(); 672579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int category = rs.getCategory(); 673579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 674579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return regsUsed.get(reg) 675579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || (category == 2 ? regsUsed.get(reg + 1) : false); 676579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 677579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 678579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 679579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Ensures that all move operations in this block occur such that 680579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * reads of any register happen before writes to that register. 681579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * NOTE: caller is expected to returnSpareRegisters()! 682579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 683579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TODO: See Briggs, et al "Practical Improvements to the Construction and 684579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Destruction of Static Single Assignment Form" section 5. a) This can 685579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * be done in three passes. 686579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 687579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param toSchedule List of instructions. Must consist only of moves. 688579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 689579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule) { 690579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet regsUsedAsSources = new BitSet(parent.getRegCount()); 691579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 692579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // TODO: Get rid of this. 693579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet regsUsedAsResults = new BitSet(parent.getRegCount()); 694579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 695579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = toSchedule.size(); 696579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 697579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int insertPlace = 0; 698579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 699579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (insertPlace < sz) { 700579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int oldInsertPlace = insertPlace; 701579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 702579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Record all registers used as sources in this block. 703579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = insertPlace; i < sz; i++) { 704579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson setRegsUsed(regsUsedAsSources, 705579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toSchedule.get(i).getSources().get(0)); 706579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 707579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson setRegsUsed(regsUsedAsResults, 708579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toSchedule.get(i).getResult()); 709579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 710579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 711579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 712579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If there are no circular dependencies, then there exists 713579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * n instructions where n > 1 whose result is not used as a source. 714579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 715579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = insertPlace; i <sz; i++) { 716579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = toSchedule.get(i); 717579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 718579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 719579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Move these n registers to the front, since they overwrite 720579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * nothing. 721579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 722579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!checkRegUsed(regsUsedAsSources, insn.getResult())) { 723579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Collections.swap(toSchedule, i, insertPlace++); 724579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 725579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 726579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 727579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 728579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If we've made no progress in this iteration, there's a 729579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * circular dependency. Split it using the temp reg. 730579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 731579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (oldInsertPlace == insertPlace) { 732579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 733579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insnToSplit = null; 734579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 735579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Find an insn whose result is used as a source. 736579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = insertPlace; i < sz; i++) { 737579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn insn = toSchedule.get(i); 738579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (checkRegUsed(regsUsedAsSources, insn.getResult()) 739579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && checkRegUsed(regsUsedAsResults, 740579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insn.getSources().get(0))) { 741579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 742579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insnToSplit = insn; 743579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 744579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We're going to split this insn; move it to the 745579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * front. 746579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 747579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Collections.swap(toSchedule, insertPlace, i); 748579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 749579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 750579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 751579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 752579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // At least one insn will be set above. 753579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 754579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insnToSplit.getResult(); 755579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec tempSpec = result.withReg( 756579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.borrowSpareRegister(result.getCategory())); 757579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 758579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn toAdd = new NormalSsaInsn( 759579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PlainInsn(Rops.opMove(result.getType()), 760579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SourcePosition.NO_INFO, 761579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson tempSpec, 762579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insnToSplit.getSources()), this); 763579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 764579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toSchedule.add(insertPlace++, toAdd); 765579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 766579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList newSources = RegisterSpecList.make(tempSpec); 767579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 768579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn toReplace = new NormalSsaInsn( 769579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PlainInsn(Rops.opMove(result.getType()), 770579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SourcePosition.NO_INFO, 771579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result, 772579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSources), this); 773579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 774579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toSchedule.set(insertPlace, toReplace); 775579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 776579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // The size changed. 777579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sz = toSchedule.size(); 778579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 779579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 780579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regsUsedAsSources.clear(); 781579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regsUsedAsResults.clear(); 782579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 783579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 784579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 785579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 786579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds {@code regV} to the live-out list for this block. This is called 787579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * by the liveness analyzer. 788579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 789579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regV register that is live-out for this block. 790579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 791579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addLiveOut (int regV) { 792579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (liveOut == null) { 793579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 794579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 795579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 796579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson liveOut.add(regV); 797579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 798579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 799579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 800579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds {@code regV} to the live-in list for this block. This is 801579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * called by the liveness analyzer. 802579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 803579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param regV register that is live-in for this block. 804579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 805579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void addLiveIn (int regV) { 806579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (liveIn == null) { 807579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 808579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 809579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 810579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson liveIn.add(regV); 811579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 812579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 813579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 814579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the set of live-in registers. Valid after register 815579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * interference graph has been generated, otherwise empty. 816579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 817579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} live-in register set. 818579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 819579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntSet getLiveInRegs() { 820579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (liveIn == null) { 821579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 822579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 823579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return liveIn; 824579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 825579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 826579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 827579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the set of live-out registers. Valid after register 828579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * interference graph has been generated, otherwise empty. 829579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 830579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} live-out register set 831579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 832579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntSet getLiveOutRegs() { 833579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (liveOut == null) { 834579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 835579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 836579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return liveOut; 837579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 838579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 839579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 840579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return true if this is the one-and-only exit block for this method 841579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 842579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean isExitBlock() { 843579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return index == parent.getExitBlockIndex(); 844579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 845579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 846579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 847579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns true if this block was last calculated to be reachable. 848579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Recalculates reachability if value has never been computed. 849579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 850579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} if reachable 851579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 852579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean isReachable() { 853579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (reachable == -1) { 854579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.computeReachability(); 855579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 856579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (reachable == 1); 857579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 858579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 859579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 860579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Sets reachability of block to specified value 861579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 862579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param reach new value of reachability for block 863579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 864579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void setReachable(int reach) { 865579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson reachable = reach; 866579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 867579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 868579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 869579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Sorts move instructions added via {@code addMoveToEnd} during 870579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * phi removal so that results don't overwrite sources that are used. 871579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * For use after all phis have been removed and all calls to 872579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * addMoveToEnd() have been made.<p> 873579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 874579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This is necessary because copy-propogation may have left us in a state 875579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * where the same basic block has the same register as a phi operand 876579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and a result. In this case, the register in the phi operand always 877579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * refers value before any other phis have executed. 878579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 879579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void scheduleMovesFromPhis() { 880579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (movesFromPhisAtBeginning > 1) { 881579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson List<SsaInsn> toSchedule; 882579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 883579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toSchedule = insns.subList(0, movesFromPhisAtBeginning); 884579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 885579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson scheduleUseBeforeAssigned(toSchedule); 886579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 887579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning); 888579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 889579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 890579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * TODO: It's actually possible that this case never happens, 891579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * because a move-exception block, having only one predecessor 892579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * in SSA form, perhaps is never on a dominance frontier. 893579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 894579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (firstNonPhiMoveInsn.isMoveException()) { 895579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (true) { 896579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 897579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We've yet to observe this case, and if it can 898579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * occur the code written to handle it probably 899579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * does not work. 900579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 901579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException( 902579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson "Unexpected: moves from " 903579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson +"phis before move-exception"); 904579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 905579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 906579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A move-exception insn must be placed first in this block 907579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We need to move it there, and deal with possible 908579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * interference. 909579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 910579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean moveExceptionInterferes = false; 911579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 912579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int moveExceptionResult 913579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = firstNonPhiMoveInsn.getResult().getReg(); 914579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 915579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 916579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Does the move-exception result reg interfere with the 917579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * phi moves? 918579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 919579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn insn : toSchedule) { 920579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (insn.isResultReg(moveExceptionResult) 921579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || insn.isRegASource(moveExceptionResult)) { 922579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson moveExceptionInterferes = true; 923579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 924579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 925579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 926579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 927579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!moveExceptionInterferes) { 928579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // This is the easy case. 929579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.remove(movesFromPhisAtBeginning); 930579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(0, firstNonPhiMoveInsn); 931579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 932579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 933579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We need to move the result to a spare reg 934579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and move it back. 935579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 936579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec originalResultSpec 937579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = firstNonPhiMoveInsn.getResult(); 938579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int spareRegister = parent.borrowSpareRegister( 939579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson originalResultSpec.getCategory()); 940579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 941579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // We now move it to a spare register. 942579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson firstNonPhiMoveInsn.changeResultReg(spareRegister); 943579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec tempSpec = 944579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson firstNonPhiMoveInsn.getResult(); 945579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 946579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.add(0, firstNonPhiMoveInsn); 947579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 948579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // And here we move it back. 949579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 950579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson NormalSsaInsn toAdd = new NormalSsaInsn( 951579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new PlainInsn( 952579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Rops.opMove(tempSpec.getType()), 953579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SourcePosition.NO_INFO, 954579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson originalResultSpec, 955579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList.make(tempSpec)), 956579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this); 957579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 958579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 959579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 960579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Place it immediately after the phi-moves, 961579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * overwriting the move-exception that was there. 962579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 963579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.set(movesFromPhisAtBeginning + 1, toAdd); 964579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 965579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 966579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 967579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 968579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 969579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (movesFromPhisAtEnd > 1) { 970579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson scheduleUseBeforeAssigned( 971579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.subList(insns.size() - movesFromPhisAtEnd - 1, 972579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.size() - 1)); 973579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 974579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 975579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Return registers borrowed here and in scheduleUseBeforeAssigned(). 976579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson parent.returnSpareRegisters(); 977579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 978579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 979579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 980579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 981579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Visits all insns in this block. 982579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 983579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param visitor {@code non-null;} callback interface 984579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 985579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void forEachInsn(SsaInsn.Visitor visitor) { 986579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // This gets called a LOT, and not using an iterator 987579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // saves a lot of allocations and reduces memory usage 988579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int len = insns.size(); 989579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < len; i++) { 990579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insns.get(i).accept(visitor); 991579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 992579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 993579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 994579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 995579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 996579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public String toString() { 997579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return "{" + index + ":" + Hex.u2(ropLabel) + '}'; 998579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 999579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 1000579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 1001579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Visitor interface for basic blocks. 1002579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 1003579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public interface Visitor { 1004579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 1005579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Indicates a block has been visited by an iterator method. 1006579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 1007579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param v {@code non-null;} block visited 1008579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param parent {@code null-ok;} parent node if applicable 1009579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 1010579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson void visitBlock (SsaBasicBlock v, SsaBasicBlock parent); 1011579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 1012579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 1013579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 1014579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Label comparator. 1015579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 1016579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static final class LabelComparator 1017579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson implements Comparator<SsaBasicBlock> { 1018579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 1019579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int compare(SsaBasicBlock b1, SsaBasicBlock b2) { 1020579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int label1 = b1.ropLabel; 1021579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int label2 = b2.ropLabel; 1022579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 1023579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (label1 < label2) { 1024579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return -1; 1025579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else if (label1 > label2) { 1026579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return 1; 1027579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 1028579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return 0; 1029579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 1030579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 1031579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 1032579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 1033