1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2008 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.util.BitIntSet; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntSet; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.ListIntSet; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Makes int sets for various parts of the optimizer. 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class SetFactory { 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * BitIntSet/ListIntSet threshold for dominance frontier sets. These 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * sets are kept per basic block until phi placement and tend to be, 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * like the CFG itself, very sparse at large sizes. 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A value of 3072 here is somewhere around 1.125mb of total bitset size. 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static final int DOMFRONT_SET_THRESHOLD_SIZE = 3072; 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * BitIntSet/ListIntSet threshold for interference graph sets. These 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * sets are kept per register until register allocation is done. 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A value of 3072 here is somewhere around 1.125mb of total bitset size. 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static final int INTERFERENCE_SET_THRESHOLD_SIZE = 3072; 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * BitIntSet/ListIntSet threshold for the live in/out sets kept by 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@link SsaBasicBlock}. These are sets of SSA registers kept per basic 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block during register allocation. 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The total size of a bitset for this would be the count of blocks 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * times the size of registers. The threshold value here is merely 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the register count, which is typically on the order of the block 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * count as well. 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static final int LIVENESS_SET_THRESHOLD_SIZE = 3072; 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Make IntSet for the dominance-frontier sets. 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param szBlocks {@code >=0;} count of basic blocks in method 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} appropriate set 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /*package*/ static IntSet makeDomFrontSet(int szBlocks) { 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return szBlocks <= DOMFRONT_SET_THRESHOLD_SIZE 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ? new BitIntSet(szBlocks) 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : new ListIntSet(); 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Make IntSet for the interference graph sets. Public because 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * InterferenceGraph is in another package. 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param countRegs {@code >=0;} count of SSA registers used in method 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} appropriate set 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static IntSet makeInterferenceSet(int countRegs) { 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return countRegs <= INTERFERENCE_SET_THRESHOLD_SIZE 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ? new BitIntSet(countRegs) 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : new ListIntSet(); 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Make IntSet for register live in/out sets. 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param countRegs {@code >=0;} count of SSA registers used in method 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} appropriate set 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /*package*/ static IntSet makeLivenessSet(int countRegs) { 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return countRegs <= LIVENESS_SET_THRESHOLD_SIZE 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ? new BitIntSet(countRegs) 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : new ListIntSet(); 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 96