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.RegisterSpec; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RopMethod; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntIterator; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Converts ROP methods to SSA Methods 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class SsaConverter { 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static final boolean DEBUG = false; 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns an SSA representation, edge-split and with phi 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * functions placed. 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rmeth input 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param paramWidth the total width, in register-units, of the method's 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * parameters 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param isStatic {@code true} if this method has no {@code this} 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * pointer argument 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return output in SSA form 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static SsaMethod convertToSsaMethod(RopMethod rmeth, 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int paramWidth, boolean isStatic) { 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaMethod result 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic); 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson edgeSplit(result); 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalVariableInfo localInfo = LocalVariableExtractor.extract(result); 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson placePhiFunctions(result, localInfo, 0); 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new SsaRenamer(result).run(); 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The exit block, added here, is not considered for edge splitting 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * or phi placement since no actual control flows to it. 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.makeExitBlock(); 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Updates an SSA representation, placing phi functions and renaming all 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * registers above a certain threshold number. 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth input 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param threshold registers below this number are unchanged 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static void updateSsaMethod(SsaMethod ssaMeth, int threshold) { 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalVariableInfo localInfo = LocalVariableExtractor.extract(ssaMeth); 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson placePhiFunctions(ssaMeth, localInfo, threshold); 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson new SsaRenamer(ssaMeth, threshold).run(); 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns an SSA represention with only the edge-splitter run. 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rmeth method to process 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param paramWidth width of all arguments in the method 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param isStatic {@code true} if this method has no {@code this} 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * pointer argument 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return an SSA represention with only the edge-splitter run 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static SsaMethod testEdgeSplit (RopMethod rmeth, int paramWidth, 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean isStatic) { 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaMethod result; 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson edgeSplit(result); 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns an SSA represention with only the steps through the 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * phi placement run. 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rmeth method to process 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param paramWidth width of all arguments in the method 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param isStatic {@code true} if this method has no {@code this} 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * pointer argument 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return an SSA represention with only the edge-splitter run 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static SsaMethod testPhiPlacement (RopMethod rmeth, int paramWidth, 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean isStatic) { 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaMethod result; 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic); 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson edgeSplit(result); 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalVariableInfo localInfo = LocalVariableExtractor.extract(result); 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson placePhiFunctions(result, localInfo, 0); 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See Appel section 19.1: 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Converts CFG into "edge-split" form, such that each node either a 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * unique successor or unique predecessor.<p> 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * In addition, the SSA form we use enforces a further constraint, 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * requiring each block with a final instruction that returns a 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * value to have a primary successor that has no other 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * predecessor. This ensures move statements can always be 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * inserted correctly when phi statements are removed. 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param result method to process 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static void edgeSplit(SsaMethod result) { 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson edgeSplitPredecessors(result); 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson edgeSplitMoveExceptionsAndResults(result); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson edgeSplitSuccessors(result); 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts Z nodes as new predecessors for every node that has multiple 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * successors and multiple predecessors. 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param result {@code non-null;} method to process 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static void edgeSplitPredecessors(SsaMethod result) { 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> blocks = result.getBlocks(); 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * New blocks are added to the end of the block list during 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * this iteration. 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = blocks.size() - 1; i >= 0; i-- ) { 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock block = blocks.get(i); 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (nodeNeedsUniquePredecessor(block)) { 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.insertNewPredecessor(); 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param block {@code non-null;} block in question 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} if this node needs to have a unique 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * predecessor created for it 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean nodeNeedsUniquePredecessor(SsaBasicBlock block) { 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Any block with that has both multiple successors and multiple 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * predecessors needs a new predecessor node. 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int countPredecessors = block.getPredecessors().cardinality(); 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int countSuccessors = block.getSuccessors().cardinality(); 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (countPredecessors > 1 && countSuccessors > 1); 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * In ROP form, move-exception must occur as the first insn in a block 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * immediately succeeding the insn that could thrown an exception. 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We may need room to insert move insns later, so make sure to split 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * any block that starts with a move-exception such that there is a 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * unique move-exception block for each predecessor. 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth method to process 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static void edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth) { 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * New blocks are added to the end of the block list during 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * this iteration. 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = blocks.size() - 1; i >= 0; i-- ) { 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock block = blocks.get(i); 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Any block that starts with a move-exception and has more than 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * one predecessor... 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!block.isExitBlock() 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && block.getPredecessors().cardinality() > 1 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && block.getInsns().get(0).isMoveException()) { 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // block.getPredecessors() is changed in the loop below. 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet preds = (BitSet)block.getPredecessors().clone(); 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = preds.nextSetBit(0); j >= 0; 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson j = preds.nextSetBit(j + 1)) { 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock predecessor = blocks.get(j); 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock zNode 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = predecessor.insertNewSuccessor(block); 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Make sure to place the move-exception as the 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * first insn. 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson zNode.getInsns().add(0, block.getInsns().get(0).clone()); 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Remove the move-exception from the original block. 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.getInsns().remove(0); 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts Z nodes for every node that needs a new 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * successor. 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param result {@code non-null;} method to process 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static void edgeSplitSuccessors(SsaMethod result) { 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> blocks = result.getBlocks(); 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * New blocks are added to the end of the block list during 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * this iteration. 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = blocks.size() - 1; i >= 0; i-- ) { 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock block = blocks.get(i); 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Successors list is modified in loop below. 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet successors = (BitSet)block.getSuccessors().clone(); 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = successors.nextSetBit(0); 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson j >= 0; j = successors.nextSetBit(j+1)) { 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock succ = blocks.get(j); 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (needsNewSuccessor(block, succ)) { 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.insertNewSuccessor(succ); 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns {@code true} if block and successor need a Z-node 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * between them. Presently, this is {@code true} if the final 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * instruction has any sources or results and the current 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * successor block has more than one predecessor. 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param block predecessor node 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param succ successor node 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} if a Z node is needed 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean needsNewSuccessor(SsaBasicBlock block, 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock succ) { 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaInsn> insns = block.getInsns(); 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaInsn lastInsn = insns.get(insns.size() - 1); 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ((lastInsn.getResult() != null) 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || (lastInsn.getSources().size() > 0)) 273579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && succ.getPredecessors().cardinality() > 1; 274579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 275579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 276579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 277579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See Appel algorithm 19.6: 278579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 279579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Place Phi functions in appropriate locations. 280579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 281579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param ssaMeth {@code non-null;} method to process. 282579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Modifications are made in-place. 283579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param localInfo {@code non-null;} local variable info, used 284579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * when placing phis 285579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param threshold registers below this number are ignored 286579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 287579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static void placePhiFunctions (SsaMethod ssaMeth, 288579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson LocalVariableInfo localInfo, int threshold) { 289579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> ssaBlocks; 290579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int regCount; 291579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int blockCount; 292579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 293579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaBlocks = ssaMeth.getBlocks(); 294579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson blockCount = ssaBlocks.size(); 295579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson regCount = ssaMeth.getRegCount() - threshold; 296579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 297579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DomFront df = new DomFront(ssaMeth); 298579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DomFront.DomInfo[] domInfos = df.run(); 299579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 300579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Bit set of registers vs block index "definition sites" 301579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet[] defsites = new BitSet[regCount]; 302579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 303579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Bit set of registers vs block index "phi placement sites" 304579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet[] phisites = new BitSet[regCount]; 305579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 306579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < regCount; i++) { 307579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson defsites[i] = new BitSet(blockCount); 308579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson phisites[i] = new BitSet(blockCount); 309579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 310579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 311579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 312579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * For each register, build a set of all basic blocks where 313579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * containing an assignment to that register. 314579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 315579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int bi = 0, s = ssaBlocks.size(); bi < s; bi++) { 316579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock b = ssaBlocks.get(bi); 317579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 318579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaInsn insn : b.getInsns()) { 319579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec rs = insn.getResult(); 320579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 321579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (rs != null && rs.getReg() - threshold >= 0) { 322579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson defsites[rs.getReg() - threshold].set(bi); 323579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 324579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 325579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 326579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 327579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 328579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("defsites"); 329579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 330579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < regCount; i++) { 331579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuilder sb = new StringBuilder(); 332579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('v').append(i).append(": "); 333579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(defsites[i].toString()); 334579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println(sb); 335579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 336579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 337579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 338579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet worklist; 339579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 340579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 341579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * For each register, compute all locations for phi placement 342579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * based on dominance-frontier algorithm. 343579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 344579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int reg = 0, s = regCount; reg < s; reg++) { 345579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int workBlockIndex; 346579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 347579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* Worklist set starts out with each node where reg is assigned. */ 348579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 349579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist = (BitSet) (defsites[reg].clone()); 350579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 351579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (0 <= (workBlockIndex = worklist.nextSetBit(0))) { 352579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.clear(workBlockIndex); 353579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntIterator dfIterator 354579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = domInfos[workBlockIndex].dominanceFrontiers.iterator(); 355579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 356579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (dfIterator.hasNext()) { 357579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int dfBlockIndex = dfIterator.next(); 358579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 359579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!phisites[reg].get(dfBlockIndex)) { 360579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson phisites[reg].set(dfBlockIndex); 361579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 362579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int tReg = reg + threshold; 363579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegisterSpec rs 364579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = localInfo.getStarts(dfBlockIndex).get(tReg); 365579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 366579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (rs == null) { 367579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(tReg); 368579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 369579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(rs); 370579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 371579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 372579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!defsites[reg].get(dfBlockIndex)) { 373579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.set(dfBlockIndex); 374579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 375579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 376579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 377579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 378579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 379579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 380579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 381579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("phisites"); 382579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 383579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < regCount; i++) { 384579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuilder sb = new StringBuilder(); 385579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('v').append(i).append(": "); 386579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(phisites[i].toString()); 387579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println(sb); 388579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 389579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 390579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 391579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 392