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.back; 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.InsnList; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpec; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rop; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RopMethod; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Rops; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.BasicRegisterMapper; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.PhiInsn; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.RegisterMapper; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.SsaBasicBlock; 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.SsaInsn; 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.ssa.SsaMethod; 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.Hex; 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.Arrays; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.Comparator; 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Converts a method in SSA form to ROP form. 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class SsaToRop { 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** local debug flag */ 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static final boolean DEBUG = false; 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} method to process */ 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final SsaMethod ssaMeth; 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code true} if the converter should attempt to minimize 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the rop-form register count 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final boolean minimizeRegisters; 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} interference graph */ 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final InterferenceGraph interference; 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Converts a method in SSA form to ROP form. 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth {@code non-null;} method to process 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param minimizeRegisters {@code true} if the converter should 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * attempt to minimize the rop-form register count 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} rop-form output 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static RopMethod convertToRopMethod(SsaMethod ssaMeth, 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean minimizeRegisters) { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return new SsaToRop(ssaMeth, minimizeRegisters).convert(); 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth {@code non-null;} method to process 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param minimizeRegisters {@code true} if the converter should 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * attempt to minimize the rop-form register count 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private SsaToRop(SsaMethod ssaMethod, boolean minimizeRegisters) { 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.minimizeRegisters = minimizeRegisters; 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.ssaMeth = ssaMethod; 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.interference = 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LivenessAnalyzer.constructInterferenceGraph(ssaMethod); 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Performs the conversion. 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} rop-form output 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private RopMethod convert() { 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson interference.dumpToStdout(); 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // These are other allocators for debugging or historical comparison: 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // allocator = new NullRegisterAllocator(ssaMeth, interference); 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // allocator = new FirstFitAllocator(ssaMeth, interference); 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterAllocator allocator = 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new FirstFitLocalCombiningAllocator(ssaMeth, interference, 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson minimizeRegisters); 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterMapper mapper = allocator.allocateRegisters(); 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("Printing reg map"); 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println(((BasicRegisterMapper)mapper).toHuman()); 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.setBackMode(); 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.mapRegisters(mapper); 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson removePhiFunctions(); 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (allocator.wantsParamsMovedHigh()) { 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson moveParametersToHighRegisters(); 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson removeEmptyGotos(); 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RopMethod ropMethod = new RopMethod(convertBasicBlocks(), 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.blockIndexToRopLabel(ssaMeth.getEntryBlockIndex())); 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ropMethod = new IdenticalBlockCombiner(ropMethod).process(); 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ropMethod; 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Removes all blocks containing only GOTOs from the control flow. 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Although much of this work will be done later when converting 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * from rop to dex, not all simplification cases can be handled 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * there. Furthermore, any no-op block between the exit block and 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * blocks containing the real return or throw statements must be 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * removed. 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void removeEmptyGotos() { 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson final ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.forEachBlockDepthFirst(false, new SsaBasicBlock.Visitor() { 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitBlock(SsaBasicBlock b, SsaBasicBlock parent) { 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaInsn> insns = b.getInsns(); 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if ((insns.size() == 1) 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (insns.get(0).getOpcode() == Rops.GOTO)) { 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet preds = (BitSet) b.getPredecessors().clone(); 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = preds.nextSetBit(0); i >= 0; 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson i = preds.nextSetBit(i + 1)) { 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock pb = blocks.get(i); 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson pb.replaceSuccessor(b.getIndex(), 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson b.getPrimarySuccessorIndex()); 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson }); 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See Appel 19.6. To remove the phi instructions in an edge-split 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * SSA representation we know we can always insert a move in a 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * predecessor block. 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void removePhiFunctions() { 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaBasicBlock block : blocks) { 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Add moves in all the pred blocks for each phi insn. 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.forEachPhiInsn(new PhiVisitor(blocks)); 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Delete the phi insns. 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.removeAllPhiInsns(); 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * After all move insns have been added, sort them so they don't 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * destructively interfere. 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaBasicBlock block : blocks) { 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.scheduleMovesFromPhis(); 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Helper for {@link #removePhiFunctions}: PhiSuccessorUpdater for 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * adding move instructions to predecessors based on phi insns. 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static class PhiVisitor implements PhiInsn.Visitor { 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaBasicBlock> blocks; 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public PhiVisitor(ArrayList<SsaBasicBlock> blocks) { 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.blocks = blocks; 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitPhiInsn(PhiInsn insn) { 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpecList sources = insn.getSources(); 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec result = insn.getResult(); 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = sources.size(); 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec source = sources.get(i); 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock predBlock = blocks.get( 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson insn.predBlockIndexForSourcesIndex(i)); 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson predBlock.addMoveToEnd(result, source); 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Moves the parameter registers, which allocateRegisters() places 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * at the bottom of the frame, up to the top of the frame to match 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Dalvik calling convention. 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void moveParametersToHighRegisters() { 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int paramWidth = ssaMeth.getParamWidth(); 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicRegisterMapper mapper 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = new BasicRegisterMapper(ssaMeth.getRegCount()); 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int regCount = ssaMeth.getRegCount(); 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < regCount; i++) { 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (i < paramWidth) { 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson mapper.addMapping(i, regCount - paramWidth + i, 1); 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson mapper.addMapping(i, i - paramWidth, 1); 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.printf("Moving %d registers from 0 to %d\n", 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson paramWidth, regCount - paramWidth); 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.mapRegisters(mapper); 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return rop-form basic block list 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private BasicBlockList convertBasicBlocks() { 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Exit block may be null. 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock exitBlock = ssaMeth.getExitBlock(); 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaMeth.computeReachability(); 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int ropBlockCount = ssaMeth.getCountReachableBlocks(); 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Don't count the exit block, if it exists and is reachable. 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ropBlockCount -= (exitBlock != null && exitBlock.isReachable()) ? 1 : 0; 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlockList result = new BasicBlockList(ropBlockCount); 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Convert all the reachable blocks except the exit block. 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int ropBlockIndex = 0; 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaBasicBlock b : blocks) { 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (b.isReachable() && b != exitBlock) { 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.set(ropBlockIndex++, convertBasicBlock(b)); 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // The exit block, which is discarded, must do nothing. 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (exitBlock != null && exitBlock.getInsns().size() != 0) { 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException( 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson "Exit block must have no insns when leaving SSA form"); 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 273579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 274579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Validates that a basic block is a valid end predecessor. It must 275579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * end in a RETURN or a THROW. Throws a runtime exception on error. 276579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 277579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param b {@code non-null;} block to validate 278579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @throws RuntimeException on error 279579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 280579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void verifyValidExitPredecessor(SsaBasicBlock b) { 281579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaInsn> insns = b.getInsns(); 282579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn lastInsn = insns.get(insns.size() - 1); 283579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Rop opcode = lastInsn.getOpcode(); 284579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 285579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (opcode.getBranchingness() != Rop.BRANCH_RETURN 286579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && opcode != Rops.THROW) { 287579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException("Exit predecessor must end" 288579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + " in valid exit statement."); 289579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 290579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 291579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 292579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 293579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Converts a single basic block to rop form. 294579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 295579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param block SSA block to process 296579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} ROP block 297579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 298579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private BasicBlock convertBasicBlock(SsaBasicBlock block) { 299579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList successorList = block.getRopLabelSuccessorList(); 300579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int primarySuccessorLabel = block.getPrimarySuccessorRopLabel(); 301579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 302579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Filter out any reference to the SSA form's exit block. 303579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 304579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Exit block may be null. 305579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock exitBlock = ssaMeth.getExitBlock(); 306579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int exitRopLabel = (exitBlock == null) ? -1 : exitBlock.getRopLabel(); 307579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 308579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (successorList.contains(exitRopLabel)) { 309579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (successorList.size() > 1) { 310579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException( 311579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson "Exit predecessor must have no other successors" 312579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + Hex.u2(block.getRopLabel())); 313579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 314579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList = IntList.EMPTY; 315579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primarySuccessorLabel = -1; 316579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 317579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson verifyValidExitPredecessor(block); 318579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 319579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 320579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 321579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList.setImmutable(); 322579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 323579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock result = new BasicBlock( 324579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.getRopLabel(), convertInsns(block.getInsns()), 325579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson successorList, 326579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson primarySuccessorLabel); 327579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 328579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 329579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 330579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 331579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 332579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Converts an insn list to rop form. 333579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 334579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaInsns {@code non-null;} old instructions 335579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} immutable instruction list 336579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 337579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private InsnList convertInsns(ArrayList<SsaInsn> ssaInsns) { 338579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int insnCount = ssaInsns.size(); 339579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson InsnList result = new InsnList(insnCount); 340579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 341579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < insnCount; i++) { 342579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.set(i, ssaInsns.get(i).toRopInsn()); 343579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 344579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 345579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.setImmutable(); 346579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 347579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 348579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 349579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 350579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 351579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * <b>Note:</b> This method is not presently used. 352579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 353579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return a list of registers ordered by most-frequently-used to 354579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * least-frequently-used. Each register is listed once and only 355579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * once. 356579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 357579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int[] getRegistersByFrequency() { 358579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int regCount = ssaMeth.getRegCount(); 359579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Integer[] ret = new Integer[regCount]; 360579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 361579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < regCount; i++) { 362579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ret[i] = i; 363579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 364579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 365579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Arrays.sort(ret, new Comparator<Integer>() { 366579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int compare(Integer o1, Integer o2) { 367579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ssaMeth.getUseListForRegister(o2).size() 368579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson - ssaMeth.getUseListForRegister(o1).size(); 369579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 370579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson }); 371579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 372579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int result[] = new int[regCount]; 373579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 374579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < regCount; i++) { 375579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result[i] = ret[i]; 376579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 377579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 378579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 379579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 380579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 381