From 9d1246d799419a8e7d96302c5787ce252e86b68d Mon Sep 17 00:00:00 2001 From: Gene Novark Date: Fri, 4 Jul 2014 15:01:11 -0400 Subject: Fix asymptotic performance issues in live variables analysis. Fix possibly-exponential runtime for DFS graph searches. Improve DFA fixpoint algorithm to correctly compute worklist of only changed nodes for each iteration. Added test that takes > 2 minutes to compile without these improvements. --- .../scala/scala/async/internal/LiveVariables.scala | 71 ++++++++++++-------- .../scala/scala/async/run/ifelse1/IfElse1.scala | 77 ++++++++++++++++++++++ 2 files changed, 120 insertions(+), 28 deletions(-) diff --git a/src/main/scala/scala/async/internal/LiveVariables.scala b/src/main/scala/scala/async/internal/LiveVariables.scala index 8753b3d..23063ba 100644 --- a/src/main/scala/scala/async/internal/LiveVariables.scala +++ b/src/main/scala/scala/async/internal/LiveVariables.scala @@ -126,14 +126,22 @@ trait LiveVariables { /** Tests if `state1` is a predecessor of `state2`. */ - def isPred(state1: Int, state2: Int, seen: Set[Int] = Set()): Boolean = - if (seen(state1)) false // breaks cycles in the CFG - else cfg get state1 match { - case Some(nextStates) => - nextStates.contains(state2) || nextStates.exists(isPred(_, state2, seen + state1)) - case None => - false - } + def isPred(state1: Int, state2: Int): Boolean = { + val seen = scala.collection.mutable.HashSet[Int]() + + def isPred0(state1: Int, state2: Int): Boolean = + if(state1 == state2) false + else if (seen(state1)) false // breaks cycles in the CFG + else cfg get state1 match { + case Some(nextStates) => + seen += state1 + nextStates.contains(state2) || nextStates.exists(isPred0(_, state2)) + case None => + false + } + + isPred0(state1, state2) + } val finalState = asyncStates.find(as => !asyncStates.exists(other => isPred(as.state, other.state))).get @@ -162,12 +170,10 @@ trait LiveVariables { LVexit = LVexit + (finalState.state -> noNull) var currStates = List(finalState) // start at final state - var pred = List[AsyncState]() // current predecessor states - var hasChanged = true // if something has changed we need to continue iterating var captured: Set[Symbol] = Set() - while (hasChanged) { - hasChanged = false + while (!currStates.isEmpty) { + var entryChanged: List[AsyncState] = Nil for (cs <- currStates) { val LVentryOld = LVentry(cs.state) @@ -176,22 +182,23 @@ trait LiveVariables { val LVentryNew = LVexit(cs.state) ++ referenced.used if (!LVentryNew.sameElements(LVentryOld)) { LVentry = LVentry + (cs.state -> LVentryNew) - hasChanged = true + entryChanged ::= cs } } - pred = currStates.flatMap(cs => asyncStates.filter(_.nextStates.contains(cs.state))) + val pred = entryChanged.flatMap(cs => asyncStates.filter(_.nextStates.contains(cs.state))) + var exitChanged: List[AsyncState] = Nil for (p <- pred) { val LVexitOld = LVexit(p.state) val LVexitNew = p.nextStates.flatMap(succ => LVentry(succ)).toSet if (!LVexitNew.sameElements(LVexitOld)) { LVexit = LVexit + (p.state -> LVexitNew) - hasChanged = true + exitChanged ::= p } } - currStates = pred + currStates = exitChanged } for (as <- asyncStates) { @@ -199,21 +206,29 @@ trait LiveVariables { AsyncUtils.vprintln(s"LVexit at state #${as.state}: ${LVexit(as.state).mkString(", ")}") } - def lastUsagesOf(field: Tree, at: AsyncState, avoid: Set[AsyncState]): Set[Int] = - if (avoid(at)) Set() - else if (captured(field.symbol)) { - Set() - } - else LVentry get at.state match { - case Some(fields) if fields.exists(_ == field.symbol) => - Set(at.state) - case _ => - val preds = asyncStates.filter(_.nextStates.contains(at.state)).toSet - preds.flatMap(p => lastUsagesOf(field, p, avoid + at)) + def lastUsagesOf(field: Tree, at: AsyncState): Set[Int] = { + val avoid = scala.collection.mutable.HashSet[AsyncState]() + + def lastUsagesOf0(field: Tree, at: AsyncState): Set[Int] = { + if (avoid(at)) Set() + else if (captured(field.symbol)) { + Set() + } + else LVentry get at.state match { + case Some(fields) if fields.exists(_ == field.symbol) => + Set(at.state) + case _ => + avoid += at + val preds = asyncStates.filter(_.nextStates.contains(at.state)).toSet + preds.flatMap(p => lastUsagesOf0(field, p)) + } } + lastUsagesOf0(field, at) + } + val lastUsages: Map[Tree, Set[Int]] = - liftables.map(fld => (fld -> lastUsagesOf(fld, finalState, Set()))).toMap + liftables.map(fld => (fld -> lastUsagesOf(fld, finalState))).toMap for ((fld, lastStates) <- lastUsages) AsyncUtils.vprintln(s"field ${fld.symbol.name} is last used in states ${lastStates.mkString(", ")}") diff --git a/src/test/scala/scala/async/run/ifelse1/IfElse1.scala b/src/test/scala/scala/async/run/ifelse1/IfElse1.scala index 587aaac..6cbe910 100644 --- a/src/test/scala/scala/async/run/ifelse1/IfElse1.scala +++ b/src/test/scala/scala/async/run/ifelse1/IfElse1.scala @@ -87,6 +87,75 @@ class TestIfElse1Class { } z } + + def pred: Future[Boolean] = async(true) + + def m5: Future[Boolean] = async { + if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(if(await(pred)) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false) + await(pred) + else + false + } } class IfElse1Spec { @@ -124,4 +193,12 @@ class IfElse1Spec { val res = Await.result(fut, 2 seconds) res mustBe (14) } + + @Test + def `await in deeply-nested if-else conditions`() { + val o = new TestIfElse1Class + val fut = o.m5 + val res = Await.result(fut, 2 seconds) + res mustBe true + } } -- cgit v1.2.3