Stack overflow when using --analyse option

[aaronbembenek]

Hi there, BASIL (commit e1ecd5f) runs into a stack overflow on the attached program when using the --analyse flag. It completes fine without that flag. Thanks!

stack-overflow-example.zip

[ailrst]

Exception in thread "main" java.lang.StackOverflowError
	at scala.collection.mutable.Builder.sizeHint(Builder.scala:69)
	at scala.collection.mutable.Builder.sizeHint$(Builder.scala:68)
	at scala.collection.mutable.HashSet.addAll(HashSet.scala:94)
	at scala.collection.mutable.HashSet$.from(HashSet.scala:31)
	at scala.collection.mutable.HashSet$.from(HashSet.scala:407)
	at scala.collection.IterableFactory.apply(Factory.scala:103)
	at scala.collection.IterableFactory.apply$(Factory.scala:103)
	at scala.collection.mutable.HashSet$.apply(HashSet.scala:407)
	at scala.collection.IterableFactory$Delegate.apply(Factory.scala:286)
	at analysis.WriteToAnalysis.getWritesTos(WriteToAnalysis.scala:26)
	at analysis.WriteToAnalysis.getWritesTos$$anonfun$1$$anonfun$1(WriteToAnalysis.scala:36)
	at scala.collection.IterableOnceOps.foreach(IterableOnce.scala:619)
	at scala.collection.IterableOnceOps.foreach$(IterableOnce.scala:617)
	at util.intrusive_list.IntrusiveList.foreach(IntrusiveList.scala:30)
	at analysis.WriteToAnalysis.getWritesTos$$anonfun$1(WriteToAnalysis.scala:28)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.IterableOnceOps.foreach(IterableOnce.scala:619)
	at scala.collection.IterableOnceOps.foreach$(IterableOnce.scala:617)
	at scala.collection.AbstractIterator.foreach(Iterator.scala:1303)
	at analysis.WriteToAnalysis.getWritesTos(WriteToAnalysis.scala:27)
	at analysis.WriteToAnalysis.getWritesTos$$anonfun$1$$anonfun$1(WriteToAnalysis.scala:36)

getWritesTo is doing a dfs of the callgraph without cutting cycles, it should be a fixed point iteration. We should be able to drop in the implementation from here

BASIL/src/main/scala/ir/transforms/ProcedureParameters.scala

Lines 247 to 342 in f70715d

	object ReadWriteAnalysis {
	sealed trait RW {
	def getRWSet: Option[RWSet] = {
	this match {
	case Top => None
	case r: RWSet => Some(r)
	}
	}
	def map[B](f: RW => RW) = {
	f(this)
	}
	}
	case class RWSet(reads: Set[Variable], writes: Set[Variable]) extends RW
	case object Top extends RW
	def onlyGlobal(r: RWSet) = r.copy(reads = r.reads.filterNot(_.isInstanceOf[LocalVar]), writes = r.writes.filterNot(_.isInstanceOf[LocalVar]))
	type st = Map[Procedure, RW]
	def addReads(r: Iterable[Variable])(i: RW) = {
	i match {
	case Top => Top
	case i: RWSet => i.copy(reads = i.reads ++ r)
	}
	}
	def addWrites(w: Iterable[Variable])(i: RW) = {
	i match {
	case Top => Top
	case i: RWSet => i.copy(writes = i.writes ++ w)
	}
	}
	def join(a: RW, b: RW): RW = {
	(a, b) match {
	case (Top, _) => Top
	case (_, Top) => Top
	case (a: RWSet, b: RWSet) => RWSet(a.reads ++ b.reads, a.writes ++ b.writes)
	}
	}
	def processProc(state: st, p: Procedure): RW = {
	p.foldLeft(state(p))((ir, s) => {
	s match {
	case s: LocalAssign => {
	ir.map(addWrites(Seq(s.lhs)))
	.map(addReads(s.rhs.variables))
	}
	case s: MemoryLoad => {
	ir.map(addWrites(Seq(s.lhs)))
	.map(addReads(s.index.variables))
	}
	case s: Return => {
	ir.map(addReads(s.outParams.flatMap(_._2.variables)))
	}
	case s: MemoryStore => {
	ir.map(addReads(s.index.variables ++ s.value.variables))
	}
	case s: DirectCall if (s.target.isExternal.contains(true)) => {
	ir.map(addReads(externalCallReads(s.target.procName)))
	.map(addWrites(externalCallWrites(s.target.procName)))
	}
	case s: DirectCall => {
	ir.map(x => join(x, state(s.target)))
	.map(addReads(s.actualParams.flatMap(_._2.variables)))
	.map(addWrites(s.outParams.flatMap(_._2.variables)))
	}
	case s: IndirectCall => Top
	case s: Assert => ir.map(addReads(s.body.variables))
	case s: Assume => ir.map(addReads(s.body.variables))
	case p: Procedure => ir
	case b: Block => ir
	case b: NOP => ir
	case b: Unreachable => ir
	case b: GoTo => ir
	}
	})
	}
	def readWriteSets(p: Program): Map[Procedure, Option[RWSet]] = {
	var state: st = Map[Procedure, RW]().withDefaultValue(RWSet(Set(), Set()))
	val worklist = mutable.Stack.from(p.procedures)
	while (worklist.nonEmpty) {
	val proc = worklist.pop
	val o = state(proc)
	val n = processProc(state, proc)
	if (o != n) {
	worklist.addAll(CallGraph.pred(proc))
	worklist.addAll(CallGraph.succ(proc))
	state = state.updated(proc, n)
	}
	}
	state.map(x => (x._1, x._2.getRWSet))
	}
	}