diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala')
| -rw-r--r-- | src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala | 553 |
1 files changed, 0 insertions, 553 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala deleted file mode 100644 index 9d48d7a0d3..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala +++ /dev/null @@ -1,553 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala -package tools.nsc -package backend.icode.analysis - -import scala.collection.{ mutable, immutable } - -/** 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. */ - sealed abstract class Value { } - case class Record(cls: Symbol, bindings: mutable.Map[Symbol, Value]) extends Value { } - /** The value of some location in memory. */ - case class Deref(l: Location) extends Value - - /** The boxed value of some location. */ - case class Boxed(l: Location) extends Value - - /** The constant value c. */ - case class Const(c: Constant) extends Value - - /** Unknown. */ - case object Unknown extends Value - - /** The bottom record. */ - object AllRecords extends Record(NoSymbol, mutable.HashMap[Symbol, Value]()) - - /** The lattice for this analysis. */ - object copyLattice extends SemiLattice { - type Bindings = mutable.Map[Location, Value] - - def emptyBinding = mutable.HashMap[Location, Value]() - - class State(val bindings: Bindings, var stack: List[Value]) { - - override def hashCode = bindings.hashCode + stack.hashCode - /* comparison with bottom is reference equality! */ - override def equals(that: Any): Boolean = that match { - case x: State => - if ((this eq bottom) || (this eq top) || (x eq bottom) || (x eq top)) this eq x - else bindings == x.bindings && stack == x.stack - case _ => - false - } - - /* 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 = { - def loop(lv: Local): Option[Value] = (bindings get LocalVar(lv)) match { - case Some(Deref(LocalVar(t))) => loop(t) - case x => x - } - loop(l) getOrElse Deref(LocalVar(l)) - } - - /** Return a local which contains the same value as this field, if any. - * If the field holds a reference to a local, the returned value is the - * binding of that local. - */ - def getFieldValue(r: Record, f: Symbol): Option[Value] = r.bindings get f map { - case Deref(LocalVar(l)) => getBinding(l) - case target @ Deref(Field(r1, f1)) => getFieldValue(r1, f1) getOrElse target - case target => target - } - - /** The same as getFieldValue, but never returns Record/Field values. Use - * this when you want to find a replacement for a field value (either a local, - * or a constant/this value). - */ - def getFieldNonRecordValue(r: Record, f: Symbol): Option[Value] = { - assert(r.bindings contains f, "Record " + r + " does not contain a field " + f) - - r.bindings(f) match { - case Deref(LocalVar(l)) => - val alias = getAlias(l) - val derefAlias = Deref(LocalVar(alias)) - - Some(getBinding(alias) match { - case Record(_, _) => derefAlias - case Deref(Field(r1, f1)) => getFieldNonRecordValue(r1, f1) getOrElse derefAlias - case Boxed(_) => derefAlias - case v => v - }) - case Deref(Field(r1, f1)) => getFieldNonRecordValue(r1, f1) - case target @ Deref(This) => Some(target) - case target @ Const(k) => Some(target) - case _ => None - } - } - - override def toString(): String = - "\nBindings: " + bindings + "\nStack: " + stack - - def dup: State = { - val b: Bindings = mutable.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(exceptional: Boolean)(a: Elem, b: Elem): Elem = { - if (a eq bottom) b - else if (b eq bottom) a - else if (a == b) a - else { - //assert(!(a.stack eq exceptionHandlerStack) && !(b.stack eq exceptionHandlerStack)) - val resStack = - if (exceptional) exceptionHandlerStack - else { -// if (a.stack.length != b.stack.length) -// throw new LubException(a, b, "Invalid stacks in states: "); - (a.stack, b.stack).zipped map { (v1, v2) => - if (v1 == v2) v1 else Unknown - } - } - -/* if (a.stack.length != b.stack.length) - throw new LubException(a, b, "Invalid stacks in states: "); - val resStack = List.map2(a.stack, b.stack) { (v1, v2) => - if (v1 == v2) v1 else Unknown - } - */ - val resBindings = mutable.HashMap[Location, Value]() - - for ((k, v) <- a.bindings if b.bindings.isDefinedAt(k) && v == b.bindings(k)) - 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.startBlock - worklist ++= (m.exh map (_.startBlock)) - m foreachBlock { b => - in(b) = lattice.bottom - out(b) = lattice.bottom - assert(out.contains(b), out) - debuglog("CopyAnalysis 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.startBlock) = new lattice.State(lattice.emptyBinding, Nil) - } - } - - override def run() { - forwardAnalysis(blockTransfer) - if (settings.debug) { - linearizer.linearize(method).foreach(b => if (b != method.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.iterator.foldLeft(in)(interpret) - - import opcodes._ - - private def retain[A, B](map: mutable.Map[A, B])(p: (A, B) => Boolean) = { - for ((k, v) <- map ; if !p(k, v)) map -= k - map - } - - /** Abstract interpretation for one instruction. */ - def interpret(in: copyLattice.Elem, i: Instruction): copyLattice.Elem = { - var out = in.dup - debuglog("- " + i + "\nin: " + in + "\n") - - i match { - case THIS(_) => - out.stack = Deref(This) :: out.stack - - case CONSTANT(k) => - if (k.tag != UnitTag) - out.stack = Const(k) :: 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 Deref(LocalVar(l)) :: _ => - in.getBinding(l) match { - case r @ Record(cls, bindings) => Deref(Field(r, field)) - case _ => Unknown - } - - case Deref(Field(r, f)) :: _ => - val fld = in.getFieldValue(r, f) - fld match { - case Some(r @ Record(cls, bindings)) if bindings.isDefinedAt(f) => - in.getFieldValue(r, f).getOrElse(Unknown) - case _ => Unknown - } - - 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 => - sys.error("Incorrect icode in " + method + ". Expecting something on the stack.") - } - out.stack = out.stack drop 1 - - case STORE_THIS(_) => - cleanReferencesTo(out, This) - out.stack = out.stack drop 1 - - case STORE_FIELD(field, isStatic) => - if (isStatic) - out.stack = out.stack.drop(1) - else { - out.stack = out.stack.drop(2) - cleanReferencesTo(out, Field(AllRecords, field)) - in.stack match { - case v :: Record(_, bindings) :: vs => - bindings += (field -> v) - case _ => () - } - } - - case CALL_PRIMITIVE(primitive) => - // TODO: model primitives - out.stack = Unknown :: out.stack.drop(i.consumed) - - case CALL_METHOD(method, style) => style match { - case Dynamic => - out = simulateCall(in, method, static = false) - - case Static(onInstance) => - if (onInstance) { - val obj = out.stack.drop(method.info.paramTypes.length).head -// if (method.isPrimaryConstructor) { - if (method.isPrimaryConstructor) { - obj match { - case Record(_, bindings) => - for (v <- out.stack.take(method.info.paramTypes.length + 1) - if v ne obj) { - bindings ++= getBindingsForPrimaryCtor(in, method) - } - case _ => () - } - // put the Record back on the stack and remove the 'returned' value - out.stack = out.stack.drop(1 + method.info.paramTypes.length) - } else - out = simulateCall(in, method, static = false) - } else - out = simulateCall(in, method, static = true) - - case SuperCall(_) => - out = simulateCall(in, method, static = false) - } - - case BOX(tpe) => - val top = out.stack.head match { - case Deref(loc) => Boxed(loc) - case _ => Unknown - } - out.stack = top :: out.stack.tail - - case UNBOX(tpe) => - val top = out.stack.head - top match { - case Boxed(loc) => Deref(loc) :: out.stack.tail - case _ => out.stack = Unknown :: out.stack.drop(1) - } - - case NEW(kind) => - val v1 = kind match { - case REFERENCE(cls) => Record(cls, mutable.HashMap[Symbol, Value]()) - case _ => Unknown - } - out.stack = v1 :: out.stack - - case CREATE_ARRAY(elem, dims) => - out.stack = Unknown :: out.stack.drop(dims) - - case IS_INSTANCE(tpe) => - out.stack = Unknown :: out.stack.drop(1) - - case CHECK_CAST(tpe) => - out.stack = Unknown :: out.stack.drop(1) - - case SWITCH(tags, labels) => - out.stack = out.stack.drop(1) - - case JUMP(whereto) => - () - - case CJUMP(success, failure, cond, kind) => - out.stack = out.stack.drop(2) - - case CZJUMP(success, failure, cond, kind) => - out.stack = out.stack.drop(1) - - case RETURN(kind) => - if (kind != UNIT) - out.stack = out.stack.drop(1) - - case THROW(_) => - out.stack = out.stack.drop(1) - - case DROP(kind) => - out.stack = out.stack.drop(1) - - case DUP(kind) => - out.stack = out.stack.head :: out.stack - - case MONITOR_ENTER() => - out.stack = out.stack.drop(1) - - case MONITOR_EXIT() => - out.stack = out.stack.drop(1) - - case SCOPE_ENTER(_) | SCOPE_EXIT(_) => - () - - case LOAD_EXCEPTION(_) => - out.stack = Unknown :: Nil - - case _ => - dumpClassesAndAbort("Unknown instruction: " + i) - } - out - } /* def interpret */ - - /** Remove all references to this local variable from both stack - * and bindings. It is called when a new assignment destroys - * previous copy-relations. - */ - final def cleanReferencesTo(s: copyLattice.State, target: Location) { - def cleanRecord(r: Record): Record = { - retain(r.bindings) { (loc, value) => - (value match { - case Deref(loc1) if (loc1 == target) => false - case Boxed(loc1) if (loc1 == target) => false - case _ => true - }) && (target match { - case Field(AllRecords, sym1) => !(loc == sym1) - case _ => true - }) - } - r - } - - s.stack = s.stack map { v => v match { - case Record(_, bindings) => - cleanRecord(v.asInstanceOf[Record]) - case Boxed(loc1) if (loc1 == target) => Unknown - case _ => v - }} - - retain(s.bindings) { (loc, value) => - (value match { - case Deref(loc1) if (loc1 == target) => false - case Boxed(loc1) if (loc1 == target) => false - case rec @ Record(_, _) => - cleanRecord(rec) - true - case _ => true - }) && - (loc match { - case l: Location if (l == target) => false - case _ => true - }) - } - } - - /** Update the state `s` after the call to `method`. - * The stack elements are dropped and replaced by the result of the call. - * If the method is impure, all bindings to record fields are cleared. - */ - final def simulateCall(state: copyLattice.State, method: Symbol, static: Boolean): copyLattice.State = { - val out = new copyLattice.State(state.bindings, state.stack) - out.stack = out.stack.drop(method.info.paramTypes.length + (if (static) 0 else 1)) - if (method.info.resultType != definitions.UnitTpe && !method.isConstructor) - out.stack = Unknown :: out.stack - if (!isPureMethod(method)) - invalidateRecords(out) - out - } - - /** Drop everything known about mutable record fields. - * - * A simple escape analysis would help here. Some of the records we - * track never leak to other methods, therefore they can not be changed. - * We should not drop their bindings in this case. A closure object - * would be such an example. Some complications: - * - * - outer pointers. An closure escapes as an outer pointer to another - * nested closure. - */ - final def invalidateRecords(state: copyLattice.State) { - def shouldRetain(sym: Symbol): Boolean = { - if (sym.isMutable) - log("dropping binding for " + sym.fullName) - !sym.isMutable - } - state.stack = state.stack map { v => v match { - case Record(cls, bindings) => - retain(bindings) { (sym, _) => shouldRetain(sym) } - Record(cls, bindings) - case _ => v - }} - - retain(state.bindings) { (loc, value) => - value match { - case Deref(Field(rec, sym)) => shouldRetain(sym) - case Boxed(Field(rec, sym)) => shouldRetain(sym) - case _ => true - } - } - } - - /** Return bindings from an object fields to the values on the stack. This - * method has to find the correct mapping from fields to the order in which - * they are passed on the stack. It works for primary constructors. - */ - private def getBindingsForPrimaryCtor(in: copyLattice.State, ctor: Symbol): mutable.Map[Symbol, Value] = { - val paramAccessors = ctor.owner.constrParamAccessors - var values = in.stack.take(1 + ctor.info.paramTypes.length).reverse.drop(1) - val bindings = mutable.HashMap[Symbol, Value]() - - debuglog("getBindings for: " + ctor + " acc: " + paramAccessors) - - var paramTypes = ctor.tpe.paramTypes - val diff = paramTypes.length - paramAccessors.length - diff match { - case 0 => () - case 1 if ctor.tpe.paramTypes.head == ctor.owner.rawowner.tpe => - // it's an unused outer - debuglog("considering unused outer at position 0 in " + ctor.tpe.paramTypes) - paramTypes = paramTypes.tail - values = values.tail - case _ => - debuglog("giving up on " + ctor + "(diff: " + diff + ")") - return bindings - } - - // this relies on having the same order in paramAccessors and - // the arguments on the stack. It should be the same! - for ((p, i) <- paramAccessors.zipWithIndex) { -// assert(p.tpe == paramTypes(i), "In: " + ctor.fullName -// + " having acc: " + (paramAccessors map (_.tpe))+ " vs. params" + paramTypes -// + "\n\t failed at pos " + i + " with " + p.tpe + " == " + paramTypes(i)) - if (p.tpe == paramTypes(i)) - bindings += (p -> values.head) - values = values.tail - } - - debuglog("\t" + bindings) - bindings - } - - /** Is symbol `m` a pure method? - */ - final def isPureMethod(m: Symbol): Boolean = - m.isGetter // abstract getters are still pure, as we 'know' - - final override def toString() = ( - if (method eq null) List("<null>") - else method.blocks map { b => - "\nIN(%s):\t Bindings: %s".format(b.label, in(b).bindings) + - "\nIN(%s):\t Stack: %s".format(b.label, in(b).stack) - } - ).mkString - - } /* class CopyAnalysis */ -} |