Scala example source code file (Liveness.scala)

This example Scala source code file (Liveness.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Scala tags/keywords

basicblock, basicblock, boolean, elem, elem, imethod, listset, listset, liveness, load_local, referenceequality, set, set, store_local

The Scala Liveness.scala source code

/* NSC -- new Scala compiler
 * Copyright 2005-2011 LAMP/EPFL
 * @author  Martin Odersky
 */


package scala.tools.nsc
package backend.icode
package analysis

import scala.collection.{ mutable, immutable }
import immutable.ListSet

/**
 * Compute liveness information for local variables.
 *
 * @author Iulian Dragos
 */
abstract class Liveness {
  val global: Global
  import global._
  import icodes._

  /** The lattice for this analysis.   */
  object livenessLattice extends SemiLattice {
    type Elem = Set[Local]
    
    object top extends ListSet[Local] with ReferenceEquality
    object bottom extends ListSet[Local] with ReferenceEquality

    def lub2(exceptional: Boolean)(a: Elem, b: Elem): Elem = a ++ b
  }

  final class LivenessAnalysis extends DataFlowAnalysis[livenessLattice.type] {
    type P = BasicBlock
    val lattice = livenessLattice

    var method: IMethod = _

    val gen: mutable.Map[BasicBlock, Set[Local]] = new mutable.HashMap()
    val kill: mutable.Map[BasicBlock, Set[Local]] = new mutable.HashMap()

    def init(m: IMethod) {
      this.method = m
      gen.clear
      kill.clear

      for (b <- m.code.blocks;
           (g, k) = genAndKill(b)) {
        gen  += (b -> g)
        kill += (b -> k)
      }

      init {
        worklist ++= m.code.blocks.toList
        m.code.blocks.foreach { b =>
          in(b)  = lattice.bottom
          out(b) = lattice.bottom
        }
      }
    }

    import opcodes._

    /** Return the gen and kill sets for this block. */
    def genAndKill(b: BasicBlock): (Set[Local], Set[Local]) = {
      var genSet = new ListSet[Local]
      var killSet = new ListSet[Local]
      for (i <- b) i match {
        case LOAD_LOCAL(local)  if (!killSet(local)) => genSet = genSet + local
        case STORE_LOCAL(local) if (!genSet(local))  => killSet = killSet + local
        case _ => ()
      }
      Pair(genSet, killSet)
    }

    override def run() {
      backwardAnalysis(blockTransfer)
      if (settings.debug.value) {
        linearizer.linearize(method).foreach(b => if (b != method.code.startBlock)
          assert(lattice.bottom != in(b),
            "Block " + b + " in " + this.method + " has input equal to bottom -- not visited?"));
      }
    }

    def blockTransfer(b: BasicBlock, out: lattice.Elem): lattice.Elem =
      gen(b) ++ (out -- kill(b))

    /** Abstract interpretation for one instruction. Very important:
     *  liveness is a backward DFA, so this method should be used to compute
     *  liveness *before* the given instruction `i'.
     */
    def interpret(out: lattice.Elem, i: Instruction): lattice.Elem = {
      var in = out

      if (settings.debug.value) {
        log("- " + i)
        log("out: " + out)
        log("\n")
      }

      i match {
        case LOAD_LOCAL(l) => in += l
        case STORE_LOCAL(l) => in -= l
        case _ =>
          ()
      }
      in
    } /* def interpret */

    override def toString(): String = {
      val buf = new StringBuilder()
      for (b <- method.code.blocks.toList) {
        buf.append("\nlive-in(" + b + ")=" + in(b) + "\nlive-out(" + b + ")=" + out(b));
      }
      buf.toString()
    }
  } /* Liveness analysis */
}