diff options
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java')
-rw-r--r-- | plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java | 128 |
1 files changed, 128 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java new file mode 100644 index 000000000000..aeab0d2cf948 --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java @@ -0,0 +1,128 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * 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 org.jetbrains.java.decompiler.modules.decompiler.decompose; + +import org.jetbrains.java.decompiler.modules.decompiler.StatEdge; +import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement; +import org.jetbrains.java.decompiler.util.VBStyleCollection; + +import java.util.List; + +public class DominatorEngine { + + private Statement statement; + + private VBStyleCollection<Integer, Integer> colOrderedIDoms = new VBStyleCollection<Integer, Integer>(); + + + public DominatorEngine(Statement statement) { + this.statement = statement; + } + + public void initialize() { + calcIDoms(); + } + + private void orderStatements() { + + for (Statement stat : statement.getReversePostOrderList()) { + colOrderedIDoms.addWithKey(null, stat.id); + } + } + + private static Integer getCommonIDom(Integer key1, Integer key2, VBStyleCollection<Integer, Integer> orderedIDoms) { + + if (key1 == null) { + return key2; + } + else if (key2 == null) { + return key1; + } + + int index1 = orderedIDoms.getIndexByKey(key1); + int index2 = orderedIDoms.getIndexByKey(key2); + + while (index1 != index2) { + if (index1 > index2) { + key1 = orderedIDoms.getWithKey(key1); + index1 = orderedIDoms.getIndexByKey(key1); + } + else { + key2 = orderedIDoms.getWithKey(key2); + index2 = orderedIDoms.getIndexByKey(key2); + } + } + + return key1; + } + + private void calcIDoms() { + + orderStatements(); + + colOrderedIDoms.putWithKey(statement.getFirst().id, statement.getFirst().id); + + // exclude first statement + List<Integer> lstIds = colOrderedIDoms.getLstKeys().subList(1, colOrderedIDoms.getLstKeys().size()); + + while (true) { + + boolean changed = false; + + for (Integer id : lstIds) { + + Statement stat = statement.getStats().getWithKey(id); + Integer idom = null; + + for (StatEdge edge : stat.getAllPredecessorEdges()) { + if (colOrderedIDoms.getWithKey(edge.getSource().id) != null) { + idom = getCommonIDom(idom, edge.getSource().id, colOrderedIDoms); + } + } + + Integer oldidom = colOrderedIDoms.putWithKey(idom, id); + if (!idom.equals(oldidom)) { + changed = true; + } + } + + if (!changed) { + break; + } + } + } + + public VBStyleCollection<Integer, Integer> getOrderedIDoms() { + return colOrderedIDoms; + } + + public boolean isDominator(Integer node, Integer dom) { + + while (!node.equals(dom)) { + + Integer idom = colOrderedIDoms.getWithKey(node); + + if (idom.equals(node)) { + return false; // root node + } + else { + node = idom; + } + } + + return true; + } +} |