blob: ea8f69c2c8705ffcb6864333dc102cdc16b21d34 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
/*
* 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 com.intellij.codeInspection.bytecodeAnalysis.asm;
import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge;
import gnu.trove.TIntArrayList;
import gnu.trove.TIntHashSet;
import gnu.trove.TIntIterator;
/**
* @author lambdamix
*/
public final class RichControlFlow {
public final ControlFlowGraph controlFlow;
public final DFSTree dfsTree;
public RichControlFlow(ControlFlowGraph controlFlow, DFSTree dfsTree) {
this.controlFlow = controlFlow;
this.dfsTree = dfsTree;
}
// Tarjan. Testing flow graph reducibility.
// Journal of Computer and System Sciences 9.3 (1974): 355-365.
public boolean reducible() {
if (dfsTree.back.isEmpty()) {
return true;
}
int size = controlFlow.transitions.length;
boolean[] loopEnters = dfsTree.loopEnters;
TIntHashSet[] cycleIncomings = new TIntHashSet[size];
// really this may be array, since dfs already ensures no duplicates
TIntArrayList[] nonCycleIncomings = new TIntArrayList[size];
int[] collapsedTo = new int[size];
int[] queue = new int[size];
int top;
for (int i = 0; i < size; i++) {
if (loopEnters[i]) {
cycleIncomings[i] = new TIntHashSet();
}
nonCycleIncomings[i] = new TIntArrayList();
collapsedTo[i] = i;
}
// from whom back connections
for (Edge edge : dfsTree.back) {
cycleIncomings[edge.to].add(edge.from);
}
// from whom ordinary connections
for (Edge edge : dfsTree.nonBack) {
nonCycleIncomings[edge.to].add(edge.from);
}
for (int w = size - 1; w >= 0 ; w--) {
top = 0;
// NB - it is modified later!
TIntHashSet p = cycleIncomings[w];
if (p == null) {
continue;
}
TIntIterator iter = p.iterator();
while (iter.hasNext()) {
queue[top++] = iter.next();
}
while (top > 0) {
int x = queue[--top];
TIntArrayList incoming = nonCycleIncomings[x];
for (int i = 0; i < incoming.size(); i++) {
int y1 = collapsedTo[incoming.getQuick(i)];
if (!dfsTree.isDescendant(y1, w)) {
return false;
}
if (y1 != w && p.add(y1)) {
queue[top++] = y1;
}
}
}
iter = p.iterator();
while (iter.hasNext()) {
collapsedTo[iter.next()] = w;
}
}
return true;
}
}
|
