wip
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/BitSubsets.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/BitSubsets.kt
index 4b884f9..628e531 100644
--- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/BitSubsets.kt
+++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/BitSubsets.kt
@@ -97,6 +97,9 @@
class BitSubsetsUnionSemilattice<T>(subsets: BitSubsets<T>) : Semilattice<BitSubsets<T>.Subset> {
override val top: BitSubsets<T>.Subset = subsets.Subset()
override fun meet(x: BitSubsets<T>.Subset, y: BitSubsets<T>.Subset): BitSubsets<T>.Subset = x union y
+ override fun copy(x: BitSubsets<T>.Subset): BitSubsets<T>.Subset {
+ TODO("Not yet implemented")
+ }
}
fun <T> BitSubsets<T>.unionSemilattice() = BitSubsetsUnionSemilattice(this)
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowAnalysis.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowAnalysis.kt
index 9399e4f..9573ed7 100644
--- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowAnalysis.kt
+++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/DataFlowAnalysis.kt
@@ -7,6 +7,8 @@
import org.jetbrains.kotlin.backend.common.ir.isUnconditional
import org.jetbrains.kotlin.ir.IrElement
+import org.jetbrains.kotlin.ir.declarations.IrClass
+import org.jetbrains.kotlin.ir.declarations.IrFunction
import org.jetbrains.kotlin.ir.expressions.IrBranch
import org.jetbrains.kotlin.ir.expressions.IrBreak
import org.jetbrains.kotlin.ir.expressions.IrContinue
@@ -35,22 +37,41 @@
* Must be idempotent, commutative and associative.
*/
fun meet(x: T, y: T): T
+ fun meetInPlace(x: T, y: T): T = meet(x, y)
+
+ fun meetAllInPlace(values: List<T>): T = values.reduce { x, y -> meet(x, y) }
+
+ fun copy(x: T): T
}
-fun <T> Semilattice<T>.meetAll(values: List<T>): T = values.reduce { x, y -> meet(x, y) }
private fun <K, T> MutableMap<K, T>.meetOrInsert(key: K, lattice: Semilattice<T>, value: T) {
- this[key] = lattice.meet(this[key] ?: lattice.top, value)
+ getOrPut(key) { lattice.top }.let {
+ lattice.meetInPlace(it, value)
+ }
+ //this[key] = lattice.meet(this[key] ?: lattice.top, value)
}
object BitsetUnionSemilattice : Semilattice<BitSet> {
override val top: BitSet = BitSet()
override fun meet(x: BitSet, y: BitSet): BitSet = x.copy().also { it.or(y) }
+ override fun copy(x: BitSet): BitSet = x.copy()
}
-class BitsetIntersectSemilattice(completeSet: BitSet) : Semilattice<BitSet> {
+class BitsetIntersectLattice(completeSet: BitSet) : Semilattice<BitSet> {
override val top: BitSet = completeSet
+ val bottom: BitSet = BitSet()
override fun meet(x: BitSet, y: BitSet): BitSet = x.copy().also { it.and(y) }
+ override fun meetInPlace(x: BitSet, y: BitSet): BitSet = x.also { it.and(y) }
+ override fun meetAllInPlace(values: List<BitSet>): BitSet {
+ val result = values.first()
+ for (v in values.drop(1)) {
+ meetInPlace(result, v)
+ }
+ return result
+ }
+ fun join(x: BitSet, y: BitSet): BitSet = x.copy().also { it.or(y) }
+ override fun copy(x: BitSet): BitSet = x.copy()
}
abstract class ForwardDataFlowAnalysis<T>(val lattice: Semilattice<T>) : IrVisitor<T, T>() {
@@ -60,6 +81,7 @@
val returnedStates = mutableMapOf<IrReturnTargetSymbol, T>()
infix fun T.meet(other: T): T = lattice.meet(this, other)
+ infix fun T.meetInPlace(other: T): T = lattice.meetInPlace(this, other)
override fun visitElement(element: IrElement, data: T): T {
var resultData = data
@@ -71,19 +93,27 @@
return resultData
}
+ override fun visitClass(declaration: IrClass, data: T): T {
+ return data;
+ }
+
+ override fun visitFunction(declaration: IrFunction, data: T): T {
+ return data;
+ }
+
final override fun visitBranch(branch: IrBranch, data: T): T = error("Should not call this")
override fun visitWhen(expression: IrWhen, data: T): T {
val conditions = expression.branches.map { it.condition }
val conditionResults = conditions.fold(listOf<T>()) { acc, next ->
val prev = if (acc.isEmpty()) data else acc.last()
- acc + listOf(next.accept(this, prev))
+ acc + listOf(lattice.copy(next.accept(this, prev)))
}
val branchResults = conditionResults.zip(expression.branches) { conditionResult, branch ->
branch.result.accept(this, conditionResult)
}
val elseResult = if (!expression.branches.last().isUnconditional()) conditionResults.last() else lattice.top
- return lattice.meetAll(branchResults + elseResult)
+ return lattice.meetAllInPlace(branchResults + elseResult)
}
final override fun visitWhileLoop(loop: IrWhileLoop, data: T): T = super.visitWhileLoop(loop, data)
@@ -96,24 +126,24 @@
var lastIterData = lattice.top
// TODO consider short-circuiting in special cases
while (true) {
- var thisIterData = lastIterData meet data
+ var thisIterData = data meetInPlace lastIterData
- thisIterData = thisIterData meet continuedStates[loop]!!
+ thisIterData = thisIterData meetInPlace continuedStates[loop]!!
if (loop is IrWhileLoop) {
- thisIterData = thisIterData meet loop.condition.accept(this, thisIterData)
+ thisIterData = thisIterData meetInPlace loop.condition.accept(this, thisIterData)
}
thisIterData = loop.body?.accept(this, thisIterData) ?: thisIterData
if (loop is IrDoWhileLoop) {
- thisIterData = thisIterData meet loop.condition.accept(this, thisIterData)
+ thisIterData = thisIterData meetInPlace loop.condition.accept(this, thisIterData)
}
- thisIterData = thisIterData meet breakedStates[loop]!!
+ thisIterData = thisIterData meetInPlace breakedStates[loop]!!
if (thisIterData == lastIterData) break
- require(thisIterData meet lastIterData == thisIterData) { "Data flow analysis diverges" }
+ //require(thisIterData meet lastIterData == thisIterData) { "Data flow analysis diverges" }
lastIterData = thisIterData
}
@@ -132,7 +162,7 @@
override fun visitReturnableBlock(expression: IrReturnableBlock, data: T): T {
val blockResult = super.visitReturnableBlock(expression, data)
- return lattice.meet(blockResult, returnedStates[expression.symbol]!!)
+ return lattice.meetInPlace(blockResult, returnedStates[expression.symbol] ?: lattice.top)
}
override fun visitReturn(expression: IrReturn, data: T): T {
@@ -146,12 +176,12 @@
// The try block may be executed only partially,
// the approximation of "either entirely or not at all" is safe.
- val afterTry = aTry.tryResult.accept(this, data) meet data
+ val afterTry = aTry.tryResult.accept(this, data) meetInPlace data
val afterCatches = aTry.catches.map { it.result.accept(this, afterTry) }
require(aTry.finallyExpression == null)
- return lattice.meetAll(listOf(afterTry) + afterCatches)
+ return lattice.meetAllInPlace(listOf(afterTry) + afterCatches)
}
override fun visitThrow(expression: IrThrow, data: T): T {
diff --git a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/StaticInitializersOptimization.kt b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/StaticInitializersOptimization.kt
index a74310a..d335abc 100644
--- a/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/StaticInitializersOptimization.kt
+++ b/kotlin-native/backend.native/compiler/ir/backend.native/src/org/jetbrains/kotlin/backend/konan/optimizations/StaticInitializersOptimization.kt
@@ -288,21 +288,23 @@
previous.and(set)
}
- val containersSemilattice = BitsetIntersectSemilattice(BitSet().also {
+ val containersSemilattice = BitsetIntersectLattice(BitSet().also {
initializedContainers.containerIds.forEach { _, id -> it.set(id) }
})
val intraproceduralAnalysis = object : ForwardDataFlowAnalysis<BitSet>(containersSemilattice) {
- private fun BitSet.withSetBit(bit: Int): BitSet =
- if (this.get(bit)) this else copy().also { it.set(bit) }
+ // TODO careful in place!!!
+ private fun BitSet.withSetBit(bit: Int): BitSet = this.also { it.set(bit) }
- private fun getResultAfterCall(function: IrSimpleFunction, set: BitSet): BitSet {
+ // FIXME careful with the returned value!!!!
+ private fun getResultAfterCall(function: IrSimpleFunction, set: BitSet?): BitSet? {
val result = initializedContainers.afterCall[function]
if (result == null) {
val file = function.calledInitializer ?: return set
- return set.withSetBit(initializedContainers.containerIds[file]!!)
+ return (set ?: BitSet()).also { it.set(initializedContainers.containerIds[file]!!) }
}
- return result.copy().also { it.or(set) }
+ if (result.isEmpty) return set
+ return (set ?: BitSet()).also { it.or(result) }
}
private fun updateResultForFunction(function: IrSimpleFunction, globalSet: BitSet, threadLocalSet: BitSet) {
@@ -313,8 +315,8 @@
private fun updateResultForFunction(function: IrSimpleFunction, set: BitSet) {
if (analysisGoal != AnalysisGoal.ComputeInitializedBeforeCall) return
- intersectInitializedFiles(initializedContainers.beforeCallGlobal, function, set.copy().also { it.or(containersWithInitializedGlobals) })
- intersectInitializedFiles(initializedContainers.beforeCallThreadLocal, function, set.copy().also { it.or(containersWithInitializedThreadLocals) })
+ intersectInitializedFiles(initializedContainers.beforeCallGlobal, function, set.also { it.or(containersWithInitializedGlobals) })
+ intersectInitializedFiles(initializedContainers.beforeCallThreadLocal, function, set.also { it.or(containersWithInitializedThreadLocals) })
}
override fun visitGetObjectValue(expression: IrGetObjectValue, data: BitSet): BitSet {
@@ -346,7 +348,7 @@
callSitesRequiringThreadLocalInitializerCall += expression
}
}
- return getResultAfterCall(actualCallee, argumentsResult)
+ return getResultAfterCall(actualCallee, argumentsResult) ?: BitSet()
}
private fun processExecuteImpl(expression: IrCall, data: BitSet): BitSet {
@@ -359,7 +361,7 @@
if (analysisGoal != AnalysisGoal.CollectCallSites) {
require(!jobInvocation.isVirtualCall) { "Expected a static call but was: ${jobInvocation.render()}" }
updateResultForFunction(jobInvocation.actualCallee,
- curData.copy().also { it.or(containersWithInitializedGlobals) }, // Globals (= shared) visible to other threads as well.
+ curData.also { it.or(containersWithInitializedGlobals) }, // Globals (= shared) visible to other threads as well.
BitSet() // A new thread is about to be created - no thread locals initialized yet.
)
}
@@ -379,20 +381,24 @@
val devirtualizedCallSite = virtualCallSites[expression] ?: return data
val arguments = expression.getArgumentsWithIr()
val argumentsResult = arguments.fold(data) { set, arg -> arg.second.accept(this, set) }
- var callResult = BitSet()
+ var callResult: BitSet? = null
var first = true
for (callSite in devirtualizedCallSite) {
val callee = callSite.actualCallee.irFunction ?: error("No IR for: ${callSite.actualCallee}")
updateResultForFunction(callee, argumentsResult)
if (first) {
- callResult = getResultAfterCall(callee, BitSet())
+ callResult = getResultAfterCall(callee, null)
first = false
} else {
- val otherSet = getResultAfterCall(callee, BitSet())
- callResult.and(otherSet)
+ val otherSet = getResultAfterCall(callee, null)
+ if (otherSet == null) {
+ callResult = null
+ } else {
+ callResult?.and(otherSet)
+ }
}
}
- return argumentsResult.copy().also { it.or(callResult) }
+ return argumentsResult.also { if (callResult != null) { it.or(callResult) } }
}
}
