[CFG] Improve the performance of control-flow info calculation
By assuming the control-flow graph visitor is pure, the change status of
each node can be tracked to only recalculate info as needed. This avoids
recalculating the data for a node, which could improve performance when
dealing with large graphs.
^KT-59670
diff --git a/compiler/fir/checkers/src/org/jetbrains/kotlin/fir/analysis/cfa/util/CfgTraverser.kt b/compiler/fir/checkers/src/org/jetbrains/kotlin/fir/analysis/cfa/util/CfgTraverser.kt
index ee8c192..d4128f2 100644
--- a/compiler/fir/checkers/src/org/jetbrains/kotlin/fir/analysis/cfa/util/CfgTraverser.kt
+++ b/compiler/fir/checkers/src/org/jetbrains/kotlin/fir/analysis/cfa/util/CfgTraverser.kt
@@ -17,33 +17,56 @@
visitor: PathAwareControlFlowGraphVisitor<K, V>,
): Map<CFGNode<*>, PathAwareControlFlowInfo<K, V>> {
val nodeMap = LinkedHashMap<CFGNode<*>, PathAwareControlFlowInfo<K, V>>()
- while (traverseOnce(visitor, nodeMap)) {
- // had changes, continue
- }
+ val changed = hashSetOf<CFGNode<*>>()
+
+ // Before the first pass, the changed set will be empty.
+ // After the first pass, the changed set will be full.
+ // Once the changed set is empty, the traversal is stable.
+ do {
+ traverseOnce(visitor, nodeMap, changed)
+ } while (changed.isNotEmpty())
+
return nodeMap
}
private fun <K : Any, V : Any> ControlFlowGraph.traverseOnce(
visitor: PathAwareControlFlowGraphVisitor<K, V>,
nodeMap: MutableMap<CFGNode<*>, PathAwareControlFlowInfo<K, V>>,
-): Boolean {
- var changed = false
+ changed: MutableSet<CFGNode<*>>,
+ previousNodesCache: MutableMap<CFGNode<*>, List<CFGNode<*>>> = hashMapOf(),
+) {
for (node in nodes) {
- // TODO, KT-59670: if data for previousNodes hasn't changed, then should be no need to recompute data for this one
- val previousData = node.previousCfgNodes.mapNotNull { source ->
- nodeMap[source]?.let {
- visitor.visitEdge(source, node, node.edgeFrom(source), it)
+ changed.remove(node)
+
+ val previousNodes = previousNodesCache.getOrPut(node) { node.previousCfgNodes }
+ if (node !in nodeMap || previousNodes.any { it in changed }) {
+ var previousData: PathAwareControlFlowInfo<K, V>? = null
+ for (previousNode in previousNodes) {
+ // TODO(KT-59670) no reason to recalculate the edge if the node data hasn't changed.
+ val nodeData = nodeMap[previousNode] ?: continue
+ val edgeData = visitor.visitEdge(
+ from = previousNode,
+ to = node,
+ data = nodeData,
+ metadata = node.edgeFrom(previousNode),
+ )
+
+ previousData = when (previousData) {
+ null -> edgeData
+ else -> visitor.mergeInfo(previousData, edgeData, node)
+ }
}
- }.reduceOrNull { a, b -> visitor.mergeInfo(a, b, node) }
- val newData = node.accept(visitor, previousData ?: emptyNormalPathInfo())
- if (newData != nodeMap.put(node, newData)) {
- changed = true
+
+ val newData = node.accept(visitor, previousData ?: emptyNormalPathInfo())
+ if (newData != nodeMap.put(node, newData)) {
+ changed.add(node)
+ }
}
+
if (node is CFGNodeWithSubgraphs<*>) {
node.subGraphs.forEach {
- changed = changed or (visitor.visitSubGraph(node, it) && it.traverseOnce(visitor, nodeMap))
+ if (visitor.visitSubGraph(node, it)) it.traverseOnce(visitor, nodeMap, changed, previousNodesCache)
}
}
}
- return changed
}
