[K/N] POC: Use RoaringBitmaps instead of CustomBitSets
diff --git a/gradle/libs.versions.toml b/gradle/libs.versions.toml index aac4ff6..7b3e289 100644 --- a/gradle/libs.versions.toml +++ b/gradle/libs.versions.toml
@@ -17,6 +17,7 @@ kotlinx-coroutines = "1.8.0" # 9.2.+ could not be applied because of https://github.com/GradleUp/shadow/issues/1874 shadow = "9.1.0" # Should be in sync with version in kotlin-native/ +roaringBitmap = "1.6.9" spdx = "0.10.0-dev-15" proguard = "7.4.2" ktor = "3.1.3" @@ -147,6 +148,7 @@ protobuf-java-lite = { module = "com.google.protobuf:protobuf-javalite", version.ref = "protobuf" } protobuf-kotlin = { module = "com.google.protobuf:protobuf-kotlin", version.ref = "protobuf" } protoc = { module = "com.google.protobuf:protoc", version.ref = "protobuf" } +roaringBitmap = { module = "org.roaringbitmap:RoaringBitmap", version.ref = "roaringBitmap" } android-gradle-plugin-gradle-api = { module = "com.android.tools.build:gradle-api", version.ref = "android-gradle-plugin" } android-gradle-plugin-gradle = { module = "com.android.tools.build:gradle", version.ref = "android-gradle-plugin" }
diff --git a/gradle/verification-metadata.xml b/gradle/verification-metadata.xml index 056cdb6..beb229f 100644 --- a/gradle/verification-metadata.xml +++ b/gradle/verification-metadata.xml
@@ -5583,6 +5583,11 @@ <sha256 value="938a2d08fe54050d7610b944d8ddc3a09355710d9e6be0aac838dbc04e9a2825" origin="Generated by Gradle"/> </artifact> </component> + <component group="org.roaringbitmap" name="RoaringBitmap" version="1.6.9"> + <artifact name="RoaringBitmap-1.6.9.jar"> + <sha256 value="68ad88d997fe3b36d7536ef0896e54bc25a298ff4faa75c61cda1ab0f619214f" origin="Generated by Gradle"/> + </artifact> + </component> <component group="org.robolectric" name="android-all" version="5.0.2_r3-robolectric-r0"> <artifact name="android-all-5.0.2_r3-robolectric-r0.jar"> <md5 value="6b57219b0d85fe3131f9628c454ca616" origin="Generated by Gradle"/>
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/build.gradle.kts b/kotlin-native/backend.native/compiler/ir/backend.native/build.gradle.kts index a035ee6..f39dc1a 100644 --- a/kotlin-native/backend.native/compiler/ir/backend.native/build.gradle.kts +++ b/kotlin-native/backend.native/compiler/ir/backend.native/build.gradle.kts
@@ -14,6 +14,7 @@ implementation(commonDependency("com.fasterxml:aalto-xml")) { isTransitive = false } implementation(commonDependency("org.codehaus.woodstox:stax2-api")) { isTransitive = false } implementation(libs.intellij.fastutil) { isTransitive = false } + implementation(libs.roaringBitmap) { isTransitive = false } implementation(intellijJDom()) implementation(intellijCore()) implementation(project(":compiler:cli"))
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/CallGraphBuilder.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/CallGraphBuilder.kt index 8750bcf..4949d0c 100644 --- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/CallGraphBuilder.kt +++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/CallGraphBuilder.kt
@@ -5,6 +5,8 @@ package org.jetbrains.kotlin.backend.konan.optimizations +import org.roaringbitmap.RoaringBitmap +import org.jetbrains.kotlin.backend.konan.util.* import org.jetbrains.kotlin.utils.forEachBit import org.jetbrains.kotlin.backend.common.pop import org.jetbrains.kotlin.backend.common.push
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowIR.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowIR.kt index 3a57500..25fa9a6 100644 --- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowIR.kt +++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowIR.kt
@@ -20,7 +20,7 @@ import org.jetbrains.kotlin.backend.konan.lower.DECLARATION_ORIGIN_BRIDGE_METHOD import org.jetbrains.kotlin.backend.konan.lower.bridgeTarget import org.jetbrains.kotlin.backend.konan.lower.getDefaultValueForOverriddenBuiltinFunction -import org.jetbrains.kotlin.backend.konan.util.CustomBitSet +import org.roaringbitmap.RoaringBitmap import org.jetbrains.kotlin.descriptors.Modality import org.jetbrains.kotlin.ir.IrElement import org.jetbrains.kotlin.ir.ObsoleteDescriptorBasedAPI @@ -425,14 +425,14 @@ class TypeHierarchy(val allTypes: Array<Type>) { private val typesSubTypes = Array(allTypes.size) { mutableListOf<Type>() } - private val allInheritors = Array(allTypes.size) { CustomBitSet() } + private val allInheritors = Array(allTypes.size) { RoaringBitmap() } init { - val visited = CustomBitSet() + val visited = RoaringBitmap() fun processType(type: Type) { - if (visited[type.index]) return - visited.set(type.index) + if (visited.contains(type.index)) return + visited.add(type.index) type.superTypes .forEach { superType -> val subTypes = typesSubTypes[superType.index] @@ -444,11 +444,11 @@ allTypes.forEach { processType(it) } } - fun inheritorsOf(type: Type): CustomBitSet { + fun inheritorsOf(type: Type): RoaringBitmap { val typeId = type.index val inheritors = allInheritors[typeId] if (!inheritors.isEmpty || type == Type.Virtual) return inheritors - inheritors.set(typeId) + inheritors.add(typeId) for (subType in typesSubTypes[typeId]) inheritors.or(inheritorsOf(subType)) return inheritors
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DevirtualizationAnalysis.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DevirtualizationAnalysis.kt index 49900d2..9d799dc 100644 --- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DevirtualizationAnalysis.kt +++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DevirtualizationAnalysis.kt
@@ -12,12 +12,9 @@ import org.jetbrains.kotlin.backend.konan.* import org.jetbrains.kotlin.backend.konan.ir.isBoxOrUnboxCall import org.jetbrains.kotlin.backend.konan.lower.loweredConstructorFunction -import org.jetbrains.kotlin.backend.konan.util.IntArrayList +import org.jetbrains.kotlin.backend.konan.util.* import org.jetbrains.kotlin.backend.konan.lower.getObjectClassInstanceFunction -import org.jetbrains.kotlin.backend.konan.util.CustomBitSet -import org.jetbrains.kotlin.backend.konan.util.LongArrayList -import org.jetbrains.kotlin.backend.konan.util.LongHashMap -import org.jetbrains.kotlin.backend.konan.util.LongHashSet +import org.roaringbitmap.RoaringBitmap import org.jetbrains.kotlin.descriptors.ClassKind import org.jetbrains.kotlin.ir.IrElement import org.jetbrains.kotlin.ir.builders.* @@ -122,8 +119,8 @@ return (exported + globalInitializers + explicitlyExported + associatedObjectConstructors + leakingThroughFunctionReferences).distinct() } - fun CustomBitSet.format(allTypes: Array<DataFlowIR.Type>): String { - return allTypes.withIndex().filter { this[it.index] }.joinToString { it.value.toString() } + fun RoaringBitmap.format(allTypes: Array<DataFlowIR.Type>): String { + return allTypes.withIndex().filter { this.contains(it.index) }.joinToString { it.value.toString() } } private val VIRTUAL_TYPE_ID = 0 // Id of [DataFlowIR.Type.Virtual]. @@ -140,7 +137,7 @@ var directCastEdges: MutableList<CastEdge>? = null var reversedCastEdges: MutableList<CastEdge>? = null - val types = CustomBitSet() + val types = RoaringBitmap() var priority = -1 @@ -181,7 +178,7 @@ val name = takeName(nameBuilder) init { - types.set(typeId) + types.add(typeId) } override fun toString(allTypes: Array<DataFlowIR.Type>): String { @@ -197,7 +194,7 @@ } } - class CastEdge(val node: Node, val suitableTypes: CustomBitSet) + class CastEdge(val node: Node, val suitableTypes: RoaringBitmap) } class Function(val symbol: DataFlowIR.FunctionSymbol, val parameters: Array<Node>, val returns: Node, val throws: Node) @@ -226,14 +223,14 @@ private val constraintGraph = ConstraintGraph() - private inline fun forEachBitInBoth(first: CustomBitSet, second: CustomBitSet, crossinline block: (Int) -> Unit) { - if (first.cardinality() < second.cardinality()) - first.forEachBit { - if (second[it]) + private inline fun forEachBitInBoth(first: RoaringBitmap, second: RoaringBitmap, crossinline block: (Int) -> Unit) { + if (first.cardinality < second.cardinality) + first.forEach { + if (second.contains(it)) block(it) } - else second.forEachBit { - if (first[it]) + else second.forEach { + if (first.contains(it)) block(it) } } @@ -257,11 +254,11 @@ fun logPathToType(reversedEdges: IntArray, node: Node, type: Int) { val nodes = constraintGraph.nodes - val visited = CustomBitSet() + val visited = RoaringBitmap() val prev = mutableMapOf<Node, Node>() var front = mutableListOf<Node>() front.add(node) - visited.set(node.id) + visited.add(node.id) lateinit var source: Node.Source bfs@while (front.isNotEmpty()) { val prevFront = front @@ -270,8 +267,8 @@ var endBfs = false reversedEdges.forEachEdge(from.id) { toId -> val to = nodes[toId] - if (!visited[toId] && to.types[type]) { - visited.set(toId) + if (!visited.contains(toId) && to.types.contains(type)) { + visited.add(toId) prev[to] = from front.add(to) if (to is Node.Source) { @@ -286,8 +283,8 @@ if (reversedCastEdges != null) for (castEdge in reversedCastEdges) { val to = castEdge.node - if (!visited[to.id] && castEdge.suitableTypes[type] && to.types[type]) { - visited.set(to.id) + if (!visited.contains(to.id) && castEdge.suitableTypes.contains(type) && to.types.contains(type)) { + visited.add(to.id) prev[to] = from front.add(to) if (to is Node.Source) { @@ -316,8 +313,8 @@ val nodesCount = nodes.size val order = IntArray(nodesCount) val multiNodes = IntArray(nodesCount) - val visited = CustomBitSet(nodesCount) - val potentialExternalVirtualCall = CustomBitSet(nodesCount) + val visited = RoaringBitmap() + val potentialExternalVirtualCall = RoaringBitmap() private fun calculateTopologicalSort() { require(directEdges.size == reversedEdges.size) @@ -325,8 +322,8 @@ val nodesStack = IntArray(nodesCount) val edgeIdsStack = IntArray(nodesCount) for (nodeId in 0 until nodesCount) { - if (visited[nodeId]) continue - visited.set(nodeId) + if (visited.contains(nodeId)) continue + visited.add(nodeId) nodesStack[0] = nodeId edgeIdsStack[0] = 0 var stackPtr = 0 @@ -338,11 +335,11 @@ stackPtr-- } else { val next = directEdges.getEdge(v, eid) - if (!visited[next]) { + if (!visited.contains(next)) { ++stackPtr nodesStack[stackPtr] = next edgeIdsStack[stackPtr] = 0 - visited.set(next) + visited.add(next) } } } @@ -356,16 +353,16 @@ var index = 0 for (i in order.size - 1 downTo 0) { val nodeIndex = order[i] - if (visited[nodeIndex]) continue + if (visited.contains(nodeIndex)) continue val start = index var cur = start multiNodes[index++] = nodeIndex - visited.set(nodeIndex) + visited.add(nodeIndex) while (cur < index) { reversedEdges.forEachEdge(multiNodes[cur++]) { - if (!visited[it]) { + if (!visited.contains(it)) { multiNodes[index++] = it - visited.set(it) + visited.add(it) } } } @@ -430,7 +427,7 @@ // Instead of having an array of boolean and erasing it - just increment the seenColor val seenEdgeTo = IntArray(numberOfNodes) - val seenBitSetTo = arrayOfNulls<CustomBitSet?>(numberOfNodes) + val seenBitSetTo = arrayOfNulls<RoaringBitmap?>(numberOfNodes) var seenColor = 0 // Cast edge processing needs to be postponed so that we know when a regular edge shadows the cast edge @@ -450,7 +447,7 @@ if (seenEdgeTo[toRootId] != seenColor) { val bitSetTo = seenBitSetTo[toRootId] if (bitSetTo == null) { - seenBitSetTo[toRootId] = edge.suitableTypes.copy() + seenBitSetTo[toRootId] = edge.suitableTypes.clone() // Since root always goes first we can safely add new edge in place nodes[fromRootId].addCastEdge(Node.CastEdge(nodes[toRootId], edge.suitableTypes)) } else { @@ -558,7 +555,7 @@ fun squashEquivalentNodes() { // These nodes might receive a final type from external world. constraintGraph.externalVirtualCalls.forEach { - potentialExternalVirtualCall.set(it.returnsNode.root().id) + potentialExternalVirtualCall.add(it.returnsNode.root().id) } val random = Random(234239874) // Just some number for reproducibility @@ -568,14 +565,14 @@ var seenColor = 0 val seenEdgeFrom = IntArray(nodes.size) - val castEdges = arrayOfNulls<CustomBitSet>(nodes.size) + val castEdges = arrayOfNulls<RoaringBitmap>(nodes.size) for (i in order.size - 1 downTo 0) { val nodeIndex = order[i] val node = nodes[nodeIndex] if (!node.isRoot) continue if (node is Node.Source) continue - if (potentialExternalVirtualCall[nodeIndex]) continue + if (potentialExternalVirtualCall.contains(nodeIndex)) continue if (!node.types.isEmpty) error("Ordinary node types should be empty (${nodeIndex})") @@ -618,7 +615,7 @@ val r = it.node.root().id if (seenEdgeFrom[r] != seenColor) { seenEdgeFrom[r] = seenColor - signature = signature xor mixHash(nodeRandomIds[r], it.suitableTypes.hashCodeLong()) + signature = signature xor mixHash(nodeRandomIds[r], it.suitableTypes.hashCode().toLong()) ++totalEdges castEdges[r] = it.suitableTypes } @@ -698,27 +695,27 @@ } private fun propagateVirtualType(directEdges: IntArray) { - val processedVirtualNodes = CustomBitSet() + val processedVirtualNodes = RoaringBitmap() fun markVirtualNodes(node: Node) { - processedVirtualNodes.set(node.id) - node.types.set(VIRTUAL_TYPE_ID) + processedVirtualNodes.add(node.id) + node.types.add(VIRTUAL_TYPE_ID) directEdges.forEachEdge(node.id) { - if (!processedVirtualNodes[it]) { + if (!processedVirtualNodes.contains(it)) { markVirtualNodes(constraintGraph.nodes[it]) } } node.directCastEdges?.forEach { - if (it.suitableTypes[VIRTUAL_TYPE_ID] && !processedVirtualNodes[it.node.id]) { + if (it.suitableTypes.contains(VIRTUAL_TYPE_ID) && !processedVirtualNodes.contains(it.node.id)) { markVirtualNodes(it.node) } } } constraintGraph.nodes.forEach { - if (it.types[VIRTUAL_TYPE_ID] && !processedVirtualNodes[it.id]) { + if (it.types.contains(VIRTUAL_TYPE_ID) && !processedVirtualNodes.contains(it.id)) { markVirtualNodes(it) } } @@ -728,20 +725,20 @@ * A node is called "useful" if any of the nodes which we are trying to devirtualize is reachable from it. * In some cases the number of "useful" nodes is on an order of magnitude less than the total number of nodes. */ - private fun collectUsefulNodes(reversedEdges: IntArray, nodesMap: Map<DataFlowIR.Node, Node>): CustomBitSet { - val usefulNodes = CustomBitSet(constraintGraph.nodes.size) + private fun collectUsefulNodes(reversedEdges: IntArray, nodesMap: Map<DataFlowIR.Node, Node>): RoaringBitmap { + val usefulNodes = RoaringBitmap() fun markReachableFrom(nodeId: Int) { - if (usefulNodes[nodeId]) return - usefulNodes.set(nodeId) + if (usefulNodes.contains(nodeId)) return + usefulNodes.add(nodeId) reversedEdges.forEachEdge(nodeId) { - if (!usefulNodes[it]) { + if (!usefulNodes.contains(it)) { markReachableFrom(it) } } constraintGraph.nodes[nodeId].reversedCastEdges?.forEach { - if (!usefulNodes[it.node.id]) { + if (!usefulNodes.contains(it.node.id)) { markReachableFrom(it.node.id) } } @@ -755,7 +752,7 @@ val receiverNode = constraintGraph.virtualCallSiteReceivers[virtualCall]?.root() ?: error("virtualCallSiteReceivers were not built for virtual call $virtualCall") - if (!receiverNode.types[VIRTUAL_TYPE_ID]) { + if (!receiverNode.types.contains(VIRTUAL_TYPE_ID)) { markReachableFrom(receiverNode.id) } } @@ -788,7 +785,7 @@ +" CAST EDGE: #${it.node.id}z casted to ${it.suitableTypes.format(allTypes)}" } allTypes.forEachIndexed { index, type -> - if (it.types[index]) + if (it.types.contains(index)) +" TYPE: $type" } } @@ -832,8 +829,8 @@ // that instance of this class could have been created by the call. constraintGraph.externalVirtualCalls.forEach { call -> val returnsNode = call.returnsNode.root() - if (call.receiverNode.root().types[VIRTUAL_TYPE_ID]) { // Called from external world. - returnsNode.types.set(call.returnType.index) + if (call.receiverNode.root().types.contains(VIRTUAL_TYPE_ID)) { // Called from external world. + returnsNode.types.add(call.returnType.index) } } } @@ -878,7 +875,7 @@ if (node is Node.Source) continue // A source has no incoming edges. - if (!usefulNodes[node.id]) continue + if (!usefulNodes.contains(node.id)) continue reversedEdges.forEachEdge(node.id) { node.types.or(constraintGraph.nodes[it].types) @@ -902,14 +899,14 @@ // Second phase - do BFS. val nodesCount = topologicalOrder.size - val marked = CustomBitSet(nodesCount) + val marked = RoaringBitmap() var front = IntArray(nodesCount) var prevFront = IntArray(nodesCount) var frontSize = 0 for ((sourceNode, edge) in badEdges) { val distNode = edge.node - if (distNode.types.orWithFilterHasChanged(sourceNode.types, edge.suitableTypes) && !marked[distNode.id]) { - marked.set(distNode.id) + if (distNode.types.orWithFilterHasChanged(sourceNode.types, edge.suitableTypes) && !marked.contains(distNode.id)) { + marked.add(distNode.id) front[frontSize++] = distNode.id } } @@ -921,26 +918,26 @@ front = prevFront prevFront = temp for (i in 0 until prevFrontSize) { - marked[prevFront[i]] = false + marked.remove(prevFront[i]) val node = constraintGraph.nodes[prevFront[i]] directEdges.forEachEdge(node.id) { distNodeId -> val distNode = constraintGraph.nodes[distNodeId] - if (!usefulNodes[distNode.id]) return@forEachEdge + if (!usefulNodes.contains(distNode.id)) return@forEachEdge - if (marked[distNode.id]) + if (marked.contains(distNode.id)) distNode.types.or(node.types) else { - if (distNode.types.orWithFilterHasChanged(node.types) && !marked[distNode.id]) { - marked.set(distNode.id) + if (distNode.types.orWithFilterHasChanged(node.types) && !marked.contains(distNode.id)) { + marked.add(distNode.id) front[frontSize++] = distNode.id } } } node.directCastEdges?.forEach { edge -> val distNode = edge.node - if (!usefulNodes[distNode.id]) return@forEach - if (distNode.types.orWithFilterHasChanged(node.types, edge.suitableTypes) && !marked[distNode.id]) { - marked.set(distNode.id) + if (!usefulNodes.contains(distNode.id)) return@forEach + if (distNode.types.orWithFilterHasChanged(node.types, edge.suitableTypes) && !marked.contains(distNode.id)) { + marked.add(distNode.id) front[frontSize++] = distNode.id } } @@ -954,7 +951,7 @@ +" Node #${multiNode.id}" allTypes.asSequence() .withIndex() - .filter { multiNode.types[it.index] }.toList() + .filter { multiNode.types.contains(it.index) }.toList() .forEach { +" ${it.value}" } } +"" @@ -969,7 +966,7 @@ assert(nodesMap[virtualCall] != null) { "Node for virtual call $virtualCall has not been built" } val receiverNode = constraintGraph.virtualCallSiteReceivers[virtualCall]?.root() ?: error("virtualCallSiteReceivers were not built for virtual call $virtualCall") - if (receiverNode.types[VIRTUAL_TYPE_ID]) { + if (receiverNode.types.contains(VIRTUAL_TYPE_ID)) { context.logMultiple { +"Unable to devirtualize callsite ${virtualCall.debugString()}" +"from ${function.symbol}" @@ -988,7 +985,7 @@ val possibleReceivers = mutableListOf<DataFlowIR.Type>() forEachBitInBoth(receiverNode.types, typeHierarchy.inheritorsOf(receiverType)) { val type = allTypes[it] - assert(instantiatingClasses[it]) { "Non-instantiating class $type" } + assert(instantiatingClasses.contains(it)) { "Non-instantiating class $type" } if (type != nothing) { context.logMultiple { +"Path to type $type" @@ -1042,7 +1039,7 @@ // Both [directEdges] and [reversedEdges] are the array representation of a graph: // for each node v the edges of that node are stored in edges[edges[v] until edges[v + 1]]. - private data class ConstraintGraphBuildResult(val instantiatingClasses: CustomBitSet, + private data class ConstraintGraphBuildResult(val instantiatingClasses: RoaringBitmap, val directEdges: IntArray, val reversedEdges: IntArray) // Here we're dividing the build process onto two phases: @@ -1059,7 +1056,7 @@ buildReversedEdges(precursor.directEdges, precursor.reversedEdgesCount)) } - private class ConstraintGraphPrecursor(val instantiatingClasses: CustomBitSet, + private class ConstraintGraphPrecursor(val instantiatingClasses: RoaringBitmap, val directEdges: IntArray, val reversedEdgesCount: IntArrayList) private fun buildReversedEdges(directEdges: IntArray, reversedEdgesCount: IntArrayList): IntArray { @@ -1125,11 +1122,11 @@ private val allTypes = typeHierarchy.allTypes private val variables = mutableMapOf<DataFlowIR.Node.Variable, Node>() private val typesVirtualCallSites = Array(allTypes.size) { mutableListOf<ConstraintGraphVirtualCall>() } - private val suitableTypes = arrayOfNulls<CustomBitSet?>(allTypes.size) + private val suitableTypes = arrayOfNulls<RoaringBitmap?>(allTypes.size) private val concreteClasses = arrayOfNulls<Node?>(allTypes.size) private val consts = arrayOfNulls<Node?>(allTypes.size) - private val virtualTypeFilter = CustomBitSet().apply { set(VIRTUAL_TYPE_ID) } - val instantiatingClasses = CustomBitSet() + private val virtualTypeFilter = RoaringBitmap().apply { add(VIRTUAL_TYPE_ID) } + val instantiatingClasses = RoaringBitmap() val bagOfEdges = LongArrayList() // Only filter duplicate edges within a function scope. That covers up to 98% of duplicates in practice. @@ -1157,7 +1154,7 @@ return if (type.isAbstract) VIRTUAL_TYPE_ID else { - if (!instantiatingClasses[type.index]) + if (!instantiatingClasses.contains(type.index)) error("Type $type is not instantiated") type.index } @@ -1252,7 +1249,7 @@ suitableTypes.forEach { it?.and(instantiatingClasses) - it?.set(VIRTUAL_TYPE_ID) + it?.add(VIRTUAL_TYPE_ID) } } @@ -1284,10 +1281,10 @@ } private fun addInstantiatingClass(type: DataFlowIR.Type) { - if (instantiatingClasses[type.index]) return - instantiatingClasses.set(type.index) + if (instantiatingClasses.contains(type.index)) return + instantiatingClasses.add(type.index) context.log { "Adding instantiating class: $type" } - checkSupertypes(type, type, CustomBitSet()) + checkSupertypes(type, type, RoaringBitmap()) } private fun processVirtualCall(virtualCall: ConstraintGraphVirtualCall, @@ -1305,8 +1302,8 @@ private fun checkSupertypes(type: DataFlowIR.Type, inheritor: DataFlowIR.Type, - seenTypes: CustomBitSet) { - seenTypes.set(type.index) + seenTypes: RoaringBitmap) { + seenTypes.add(type.index) context.logMultiple { +"Checking supertype $type of $inheritor" @@ -1329,14 +1326,14 @@ } } for (superType in type.superTypes) { - if (!seenTypes[superType.index]) + if (!seenTypes.contains(superType.index)) checkSupertypes(superType, inheritor, seenTypes) } } private fun createCastEdge(node: Node, type: DataFlowIR.Type): Node.CastEdge { if (suitableTypes[type.index] == null) - suitableTypes[type.index] = typeHierarchy.inheritorsOf(type).copy() + suitableTypes[type.index] = typeHierarchy.inheritorsOf(type).clone() return Node.CastEdge(node, suitableTypes[type.index]!!) }
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/util/CustomBitSet.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/util/CustomBitSet.kt deleted file mode 100644 index 3fb4ade..0000000 --- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/util/CustomBitSet.kt +++ /dev/null
@@ -1,187 +0,0 @@ -/* - * Copyright 2010-2025 JetBrains s.r.o. and Kotlin Programming Language contributors. - * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. - */ - -package org.jetbrains.kotlin.backend.konan.util - -/** - * Provides some bulk operations needed for devirtualization - */ -internal class CustomBitSet private constructor(size: Int, data: LongArray) { - var size = size - private set - private var data = data - - constructor() : this(0, EMPTY) - - constructor(nodesCount: Int) : this(0, LongArray((nodesCount shr 6) + 1)) - - private fun ensureCapacity(index: Int) { - if (data.size <= index) { - val oldData = data - data = LongArray((oldData.size * 2).coerceAtLeast(index + 1)) - oldData.copyInto(data) - } - if (size <= index) size = index + 1 - } - - fun set(bitIndex: Int) { - val index = bitIndex shr 6 - val offset = bitIndex and 0x3f - ensureCapacity(index) - data[index] = data[index] or (1L shl offset) - } - - fun clear(bitIndex: Int) { - val index = bitIndex shr 6 - val offset = bitIndex and 0x3f - ensureCapacity(index) - data[index] = data[index] and (1L shl offset).inv() - } - - operator fun get(bitIndex: Int): Boolean { - val index = bitIndex shr 6 - val offset = bitIndex and 0x3f - return index < size && (data[index] and (1L shl offset)) != 0L - } - - operator fun set(bitIndex: Int, value: Boolean) { - if (value) { - set(bitIndex) - } else { - clear(bitIndex) - } - } - - fun cardinality(): Int { - var cardinality = 0 - for (i in 0 until size) { - cardinality += data[i].countOneBits() - } - return cardinality - } - - inline fun forEachBit(block: (Int) -> Unit) { - for (index in 0 until size) { - var d = data[index] - val idx = index shl 6 - while (d != 0L) { - val t = d and -d - d -= t - block(idx + t.countTrailingZeroBits()) - } - } - } - - fun clear() { - data.fill(0L) - size = 0 - } - - fun or(another: CustomBitSet) { - val adata = another.data - val asize = another.size - ensureCapacity(asize - 1) - for (i in 0 until asize) { - data[i] = data[i] or adata[i] - } - } - - fun orWithFilterHasChanged(another: CustomBitSet): Boolean { - val adata = another.data - val asize = another.size - ensureCapacity(asize - 1) - var acc = 0L - for (i in 0 until asize) { - val d = data[i] - val dd = d or adata[i] - acc = acc or (dd xor d) - data[i] = dd - } - return acc != 0L - } - - - fun orWithFilterHasChanged(another: CustomBitSet, filter: CustomBitSet): Boolean { - val fdata = filter.data - val fsize = filter.size - val adata = another.data - val asize = another.size - ensureCapacity(asize - 1) - - var acc = 0L - for (i in 0 until asize.coerceAtMost(fsize)) { - val d = data[i] - val fd = fdata[i] - val dd = d or (adata[i] and fd) - acc = acc or (dd xor d) - data[i] = dd - } - - return acc != 0L - } - - fun and(another: CustomBitSet) { - val adata = another.data - val asize = another.size - ensureCapacity(asize - 1) - for (i in 0 until asize) { - data[i] = data[i] and adata[i] - } - for (i in asize until size) { - data[i] = 0L - } - } - - fun andNot(another: CustomBitSet) { - val adata = another.data - val asize = another.size - ensureCapacity(asize - 1) - for (i in 0 until asize) { - data[i] = data[i] and adata[i].inv() - } - } - - fun copy(): CustomBitSet { - return CustomBitSet(size, data.copyOf()) - } - - val isEmpty - get(): Boolean { - for (i in 0 until size) { - if (data[i] != 0L) return false - } - return true - } - - override fun hashCode(): Int { - val h = hashCodeLong() - return ((h shr 32) xor h).toInt() - } - - override fun equals(other: Any?): Boolean { - if (other !is CustomBitSet) return false - if (size != other.size) return false - - for (i in 0 until size) { - if (data[i] != other.data[i]) return false - } - - return true - } - - fun hashCodeLong(): Long { - var h = 1234L - - for (i in size - 1 downTo 0) { - h = h xor (data[i] * (i + 1)) - } - - return h - } - - companion object { - private val EMPTY = LongArray(0) - } -}
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/util/RoaringBitmapExtensions.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/util/RoaringBitmapExtensions.kt new file mode 100644 index 0000000..dcfa7a4 --- /dev/null +++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/util/RoaringBitmapExtensions.kt
@@ -0,0 +1,28 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.backend.konan.util + +import org.roaringbitmap.RoaringBitmap + +fun RoaringBitmap.orWithFilterHasChanged(another: RoaringBitmap): Boolean { + val sizeBefore = this.cardinality + this.or(another) + return this.cardinality != sizeBefore +} + +fun RoaringBitmap.orWithFilterHasChanged(another: RoaringBitmap, filter: RoaringBitmap): Boolean { + val sizeBefore = this.cardinality + val toAdd = RoaringBitmap.and(another, filter) + this.or(toAdd) + return this.cardinality != sizeBefore +} + +inline fun RoaringBitmap.forEachBit(block: (Int) -> Unit) { + val it = this.intIterator + while (it.hasNext()) { + block(it.next()) + } +}