diff options
Diffstat (limited to 'dx/src/com/android/dx/ssa/DomFront.java')
| -rw-r--r-- | dx/src/com/android/dx/ssa/DomFront.java | 204 |
1 files changed, 204 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/ssa/DomFront.java b/dx/src/com/android/dx/ssa/DomFront.java new file mode 100644 index 0000000..941a317 --- /dev/null +++ b/dx/src/com/android/dx/ssa/DomFront.java @@ -0,0 +1,204 @@ +/* + * Copyright (C) 2007 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.dx.ssa; + +import com.android.dx.util.IntSet; +import com.android.dx.util.BitIntSet; +import com.android.dx.util.ListIntSet; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.BitSet; + +/** + * Calculates the dominance-frontiers of a methot's basic blocks. + * Algorithm from "A Simple, Fast Dominance Algorithm" by Cooper, + * Harvey, and Kennedy; transliterated to Java. + */ +public class DomFront { + /** local debug flag */ + private static boolean DEBUG = false; + + /** {@code non-null;} method being processed */ + private final SsaMethod meth; + + private final ArrayList<SsaBasicBlock> nodes; + + private final DomInfo[] domInfos; + + /** + * Dominance-frontier information for a single basic block. + */ + public static class DomInfo { + /** + * {@code null-ok;} the dominance frontier set indexed by + * block index + */ + public IntSet dominanceFrontiers; + + /** {@code >= 0 after run();} the index of the immediate dominator */ + public int idom = -1; + } + + /** + * Constructs instance. Call {@link DomFront#run} to process. + * + * @param meth {@code non-null;} method to process + */ + public DomFront(SsaMethod meth) { + this.meth = meth; + nodes = meth.getBlocks(); + + int szNodes = nodes.size(); + domInfos = new DomInfo[szNodes]; + + for (int i = 0; i < szNodes; i++) { + domInfos[i] = new DomInfo(); + } + } + + /** + * Calculates the dominance frontier information for the method. + * + * @return {@code non-null;} an array of DomInfo structures + */ + public DomInfo[] run() { + int szNodes = nodes.size(); + + if (DEBUG) { + for (int i = 0; i < szNodes; i++) { + SsaBasicBlock node = nodes.get(i); + System.out.println("pred[" + i + "]: " + + node.getPredecessors()); + } + } + + Dominators methDom = Dominators.make(meth, domInfos, false); + + if (DEBUG) { + for (int i = 0; i < szNodes; i++) { + DomInfo info = domInfos[i]; + System.out.println("idom[" + i + "]: " + + info.idom); + } + } + + buildDomTree(); + + if (DEBUG) { + debugPrintDomChildren(); + } + + for (int i = 0; i < szNodes; i++) { + domInfos[i].dominanceFrontiers + = SetFactory.makeDomFrontSet(szNodes); + } + + calcDomFronts(); + + if (DEBUG) { + for (int i = 0; i < szNodes; i++) { + System.out.println("df[" + i + "]: " + + domInfos[i].dominanceFrontiers); + } + } + + return domInfos; + } + + private void debugPrintDomChildren() { + int szNodes = nodes.size(); + + for (int i = 0; i < szNodes; i++) { + SsaBasicBlock node = nodes.get(i); + StringBuffer sb = new StringBuffer(); + + sb.append('{'); + boolean comma = false; + for (SsaBasicBlock child : node.getDomChildren()) { + if (comma) { + sb.append(','); + } + sb.append(child); + comma = true; + } + sb.append('}'); + + System.out.println("domChildren[" + node + "]: " + + sb); + } + } + + /** + * The dominators algorithm leaves us knowing who the immediate dominator + * is for each node. This sweeps the node list and builds the proper + * dominance tree. + */ + private void buildDomTree() { + int szNodes = nodes.size(); + + for (int i = 0; i < szNodes; i++) { + DomInfo info = domInfos[i]; + + if (info.idom == -1) continue; + + SsaBasicBlock domParent = nodes.get(info.idom); + domParent.addDomChild(nodes.get(i)); + } + } + + /** + * Calculates the dominance-frontier set. + * from "A Simple, Fast Dominance Algorithm" by Cooper, + * Harvey, and Kennedy; transliterated to Java. + */ + private void calcDomFronts() { + int szNodes = nodes.size(); + + for (int b = 0; b < szNodes; b++) { + SsaBasicBlock nb = nodes.get(b); + DomInfo nbInfo = domInfos[b]; + BitSet pred = nb.getPredecessors(); + + if (pred.cardinality() > 1) { + for (int i = pred.nextSetBit(0); i >= 0; + i = pred.nextSetBit(i + 1)) { + + for (int runnerIndex = i; + runnerIndex != nbInfo.idom; /* empty */) { + /* + * We can stop if we hit a block we already + * added label to, since we must be at a part + * of the dom tree we have seen before. + */ + if (runnerIndex == -1) break; + + DomInfo runnerInfo = domInfos[runnerIndex]; + + if (runnerInfo.dominanceFrontiers.has(b)) { + break; + } + + // Add b to runner's dominance frontier set. + runnerInfo.dominanceFrontiers.add(b); + runnerIndex = runnerInfo.idom; + } + } + } + } + } +} |