| /* |
| * 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 { |
| private static boolean DEBUG = false; |
| |
| 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 { |
| /** non-null; the dominance frontier set indexed by block index */ |
| IntSet dominanceFrontiers; |
| /** >= 0 after run(); the index of the immediate dominator */ |
| int idom = -1; |
| /** depth-first traversal index */ |
| int traversalIndex; |
| } |
| |
| /** |
| * Constructs instance. Call {@link DomFront#run} to process. |
| * @param meth |
| */ |
| 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 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 = new Dominators(domInfos, false); |
| methDom.run(meth); |
| |
| 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]; |
| 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 |
| ;) { |
| // 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. |
| 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; |
| } |
| } |
| } |
| } |
| } |
| } |