copypropagation.scala

来自「JAVA 语言的函数式编程扩展」· SCALA 代码 · 共 534 行 · 第 1/2 页

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

// $Id: CopyPropagation.scala 14416 2008-03-19 01:17:25Z mihaylov $

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

import scala.collection.mutable.{Map, HashMap}
import scala.tools.nsc.symtab.Flags.DEFERRED

/** A modified copy-propagation like analysis. It 
 *  is augmented with a record-like value which is used
 *  to represent closures.
 *
 *  @author Iulian Dragos
 */
abstract class CopyPropagation {
  val global: Global
  import global._
  import icodes._

  /** Locations can be local variables, this, and fields. */
  abstract sealed class Location;
  case class LocalVar(l: Local) extends Location
  case class Field(r: Record, sym: Symbol) extends Location
  case object This extends Location

  /** Values that can be on the stack. */
  abstract class Value {
    def isRecord = false
  }
  case class Record(cls: Symbol, bindings: Map[Symbol, Value]) extends Value {
    override def isRecord = true
  }
  case class Deref(l: Location) extends Value
  case class Boxed(l: Location) extends Value
  case object Unknown extends Value
  object AllRecords extends Record(NoSymbol, new HashMap[Symbol, Value])

  /** The lattice for this analysis.   */
  object copyLattice extends CompleteLattice {
    type Bindings = Map[Location, Value]

    def emptyBinding = new HashMap[Location, Value]()

    class State(val bindings: Bindings, var stack: List[Value]) {
      override def equals(that: Any): Boolean = 
        (this eq that.asInstanceOf[AnyRef]) ||
        that.isInstanceOf[State] && {
          val other = that.asInstanceOf[State]

          /* comparison with bottom is reference equality! */
          if ((other eq bottom) || (this eq bottom))
            (this eq other)
          else {
            this.bindings == other.bindings &&
            List.forall2(this.stack, other.stack) { (a, b) => a == b }
          }
        }

      /* Return an alias for the given local. It returns the last
       * local in the chain of aliased locals. Cycles are not allowed
       * to exist (by construction).
       */
      def getAlias(l: Local): Local = {
        var target = l
        var stop = false
        
        while (bindings.isDefinedAt(LocalVar(target)) && !stop) {
          bindings(LocalVar(target)) match {
            case Deref(LocalVar(t)) => target = t
            case _ => stop = true
          }
        }
        target
      }

      /* Return the value bound to the given local. */
      def getBinding(l: Local): Value = {
        var target = l
        var stop = false
        var value: Value = Deref(LocalVar(target))
        
        while (bindings.isDefinedAt(LocalVar(target)) && !stop) {
//          Console.println("finding binding for " + target)
          value = bindings(LocalVar(target))
          value match {
            case Deref(LocalVar(t)) => target = t
            case _ => stop = true
          }
        }
        value
      }

      /* Return the binding for the given field of the given record */
      def getBinding(r: Record, f: Symbol): Value = {
        assert(r.bindings.isDefinedAt(f),
               "Record " + r + " does not contain a field " + f);

        var target: Value = r.bindings(f);
        target match {
          case Deref(LocalVar(sym)) => getBinding(sym)
          case _ => target
        }
      }
      
      /** Return a local which contains the same value as this field, if any. */
      def getLocalForField(r: Record, f: Symbol): Option[Value] = {
        assert(r.bindings.isDefinedAt(f),
            "Record " + r + " does not contain a field " + f);

        var target: Value = r.bindings(f)
        target match {
          case Deref(LocalVar(l)) => Some(Deref(LocalVar(getAlias(l))))
          case Deref(This)    => Some(target)
          case _  => None
        }
      }

      override def toString(): String =
        "\nBindings: " + bindings + "\nStack: " + stack;

      def dup: State = {
        val b: Bindings = new HashMap()
        b ++= bindings
        new State(b, stack)
      }
    }

    type Elem = State

    val top    = new State(emptyBinding, Nil)
    val bottom = new State(emptyBinding, Nil)

    val exceptionHandlerStack = Unknown :: Nil

    def lub2(a: Elem, b: Elem): Elem = {
      if (a eq bottom)      b
      else if (b eq bottom) a
      else if (a == b) a
      else {
        val resStack = 
          if (a.stack eq exceptionHandlerStack) a.stack
          else if (b.stack eq exceptionHandlerStack) b.stack
          else {
            if (a.stack.length != b.stack.length)
              throw new LubError(a, b, "Invalid stacks in states: ");
            List.map2(a.stack, b.stack) { (v1, v2) => 
              if (v1 == v2) v1 else Unknown 
            }
          }
      
/*        if (a.stack.length != b.stack.length)
          throw new LubError(a, b, "Invalid stacks in states: ");
        val resStack = List.map2(a.stack, b.stack) { (v1, v2) => 
          if (v1 == v2) v1 else Unknown 
        }
        */
        val commonPairs = a.bindings.toList intersect (b.bindings.toList)
        val resBindings = new HashMap[Location, Value]
        for ((k, v) <- commonPairs)
          resBindings += (k -> v);
        new State(resBindings, resStack)
      }
    }
  }

  final class CopyAnalysis extends DataFlowAnalysis[copyLattice.type] {
    type P = BasicBlock
    val lattice = copyLattice

    var method: IMethod = _

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

      init {
        worklist += m.code.startBlock
        worklist ++= (m.exh map (_.startBlock))
        m.code.blocks.foreach { b =>
          in(b)  = lattice.bottom
          out(b) = lattice.bottom
          assert(out.contains(b))
          log("Added point: " + b)
        } 
        m.exh foreach { e =>
          in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, copyLattice.exceptionHandlerStack);
        }

        // first block is special: it's not bottom, but a precisely defined state with no bindings
        in(m.code.startBlock) = new lattice.State(lattice.emptyBinding, Nil);
      }
    }

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

    def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem =
      b.toList.foldLeft(in)(interpret)
    
    import opcodes._

    /** Abstract interpretation for one instruction. */
    def interpret(in: copyLattice.Elem, i: Instruction): copyLattice.Elem = {
      var out = in.dup

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

      i match {
        case THIS(_) =>
          out.stack = Deref(This) :: out.stack

        case CONSTANT(k) =>
          if (k.tag != UnitTag)
            out.stack = Unknown :: out.stack;
          
        case LOAD_ARRAY_ITEM(_) =>
          out.stack = (Unknown :: out.stack.drop(2))

        case LOAD_LOCAL(local) =>
          out.stack = Deref(LocalVar(local)) :: out.stack

        case LOAD_FIELD(field, isStatic) =>
          if (isStatic)
            out.stack = Unknown :: out.stack; /* ignore static fields */
          else {
            val v1 = in.stack match {
              case (r @ Record(cls, bindings)) :: xs =>
                Deref(Field(r, field))

              case _ => Unknown
            }
            out.stack = v1 :: out.stack.drop(1)
          }
            
        case LOAD_MODULE(module) =>
          out.stack = Unknown :: out.stack
          
        case STORE_ARRAY_ITEM(kind) =>
          out.stack = out.stack.drop(3)

        case STORE_LOCAL(local) =>
          cleanReferencesTo(out, LocalVar(local))
          in.stack match {
            case Unknown :: xs => ()
            case v :: vs => 
              v match {
                case Deref(LocalVar(other)) =>
                  if (other != local) 
                    out.bindings += (LocalVar(local) -> v);
                case _ =>
                  out.bindings += (LocalVar(local) -> v)
              }
            case Nil =>
              Predef.error("Incorrect icode in " + method + ". Expecting something on the stack.")