diff options
7 files changed, 307 insertions, 13 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index 52ebe21a93..07a2142f8b 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -90,7 +90,7 @@ trait BasicBlocks { /** Return an iterator over the instructions in this basic block. */ def elements: Iterator[Instruction] = - if (closed) instrs.elements else instructionList.elements + if (closed) instrs.elements else instructionList.reverse.elements /** return the underlying array of instructions */ def getArray: Array[Instruction] = { diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala index 0fe5f852f2..c369ed0cc0 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala @@ -66,6 +66,8 @@ trait TypeStacks { self: ICodes => prefix } + def apply(n: Int): TypeKind = types(n) + /** * A TypeStack aggress with another one if they have the same * length and each type kind agrees position-wise. Two diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala index aa0fa31f0f..07e0d0711b 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -24,7 +24,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] { val visited: HashSet[P] = new HashSet /** collect statistics? */ - var stat = false + var stat = true /** the number of times we iterated before reaching a fixpoint. */ var iterations = 0 diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala index ddb8125291..942b335f1e 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -7,7 +7,7 @@ package scala.tools.nsc.backend.icode.analysis -import scala.collection.mutable.{Map, HashMap} +import scala.collection.{mutable, immutable} /** A data-flow analysis on types, that works on <code>ICode</code>. * @@ -59,7 +59,7 @@ abstract class TypeFlowAnalysis { } /** A map which returns the bottom type for unfound elements */ - class VarBinding extends HashMap[icodes.Local, icodes.TypeKind] { + class VarBinding extends mutable.HashMap[icodes.Local, icodes.TypeKind] { override def get(l: icodes.Local) = super.get(l) match { case Some(t) => Some(t) case None => Some(typeLattice.bottom) @@ -101,6 +101,8 @@ abstract class TypeFlowAnalysis { } } + val timer = new Timer + class MethodTFA extends DataFlowAnalysis[typeFlowLattice.type] { import icodes._ import icodes.opcodes._ @@ -135,12 +137,13 @@ abstract class TypeFlowAnalysis { else reinit { for (b <- m.code.blocks; if !in.isDefinedAt(b)) { for (p <- b.predecessors) { - worklist += p - if (out.isDefinedAt(p)) + if (out.isDefinedAt(p)) { in(b) = out(p) - else + worklist += p + } +/* else in(b) = typeFlowLattice.bottom - } +*/ } out(b) = typeFlowLattice.bottom } for (exh <- m.exh; if !in.isDefinedAt(exh.startBlock)) { @@ -156,18 +159,215 @@ abstract class TypeFlowAnalysis { } def run = { + timer.start forwardAnalysis(blockTransfer) + timer.stop if (settings.debug.value) { linearizer.linearize(method).foreach(b => if (b != method.code.startBlock) assert(visited.contains(b), "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? .." + visited)); } + println("iterations: " + iterations + " for " + method.code.blocks.size) } def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { - b.toList.foldLeft(in)(interpret) + b.foldLeft(in)(interpret) } + /** The flow function of a given basic block. */ + var flowFun: immutable.Map[BasicBlock, TransferFunction] = new immutable.HashMap + + /** Fill flowFun with a transfer function per basic block. */ +/* private def buildFlowFunctions(blocks: List[BasicBlock]) { + def transfer(b: BasicBlock): TransferFunction = { + var gens: List[Gen] = Nil + var consumed: Int = 0 + val stack = new SimulatedStack + + for (instr <- b) instr match { + case THIS(clasz) => + stack push toTypeKind(clasz.tpe) + + case CONSTANT(const) => + stack push toTypeKind(const.tpe) + + case LOAD_ARRAY_ITEM(kind) => + stack.pop2 + stack.push(kind) + + case LOAD_LOCAL(local) => + val t = bindings(local) + stack push (if (t == typeLattice.bottom) local.kind else t) + + case LOAD_FIELD(field, isStatic) => + if (!isStatic) + stack.pop + stack push toTypeKind(field.tpe) + + case LOAD_MODULE(module) => + stack push toTypeKind(module.tpe) + + case STORE_ARRAY_ITEM(kind) => + stack.pop3 + + case STORE_LOCAL(local) => + val t = stack.pop + bindings += (local -> t) + + case STORE_THIS(_) => + stack.pop + + case STORE_FIELD(field, isStatic) => + if (isStatic) + stack.pop + else + stack.pop2 + + case CALL_PRIMITIVE(primitive) => + primitive match { + case Negation(kind) => + stack.pop; stack.push(kind) + case Test(_, kind, zero) => + stack.pop + if (!zero) stack.pop + stack push BOOL; + case Comparison(_, _) => + stack.pop2 + stack push INT + + case Arithmetic(op, kind) => + stack.pop + if (op != NOT) + stack.pop + val k = kind match { + case BYTE | SHORT | CHAR => INT + case _ => kind + } + stack push k + + case Logical(op, kind) => + stack.pop2 + stack push kind + + case Shift(op, kind) => + stack.pop2 + stack push kind + + case Conversion(src, dst) => + stack.pop + stack push dst + + case ArrayLength(kind) => + stack.pop + stack push INT + + case StartConcat => + stack.push(ConcatClass) + + case EndConcat => + stack.pop + stack.push(STRING) + + case StringConcat(el) => + stack.pop2 + stack push ConcatClass + } + + case CALL_METHOD(method, style) => style match { + case Dynamic => + stack.pop(1 + method.info.paramTypes.length) + stack.push(toTypeKind(method.info.resultType)) + + case Static(onInstance) => + if (onInstance) { + stack.pop(1 + method.info.paramTypes.length) + if (!method.isConstructor) + stack.push(toTypeKind(method.info.resultType)); + } else { + stack.pop(method.info.paramTypes.length) + stack.push(toTypeKind(method.info.resultType)) + } + + case SuperCall(mix) => + stack.pop(1 + method.info.paramTypes.length) + stack.push(toTypeKind(method.info.resultType)) + } + + case BOX(kind) => + stack.pop + stack.push(BOXED(kind)) + + case UNBOX(kind) => + stack.pop + stack.push(kind) + + case NEW(kind) => + stack.push(kind) + + case CREATE_ARRAY(elem, dims) => + stack.pop(dims) + stack.push(ARRAY(elem)) + + case IS_INSTANCE(tpe) => + stack.pop + stack.push(BOOL) + + case CHECK_CAST(tpe) => + stack.pop + stack.push(tpe) + + case SWITCH(tags, labels) => + stack.pop + + case JUMP(whereto) => + () + + case CJUMP(success, failure, cond, kind) => + stack.pop2 + + case CZJUMP(success, failure, cond, kind) => + stack.pop + + case RETURN(kind) => + if (kind != UNIT) + stack.pop; + + case THROW() => + stack.pop + + case DROP(kind) => + stack.pop + + case DUP(kind) => + stack.push(stack.head) + + case MONITOR_ENTER() => + stack.pop + + case MONITOR_EXIT() => + stack.pop + + case SCOPE_ENTER(_) | SCOPE_EXIT(_) => + () + + case LOAD_EXCEPTION() => + stack.pop(stack.length) + stack.push(typeLattice.Object) + + case _ => + dump + abort("Unknown instruction: " + i) + + } + + new TransferFunction(consumed, gens) + } + + for (val b <- blocks) { + flowFun = flowFun + (b -> transfer(b)) + } + } +*/ /** Abstract interpretation for one instruction. */ def interpret(in: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = { val out = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) @@ -357,5 +557,99 @@ abstract class TypeFlowAnalysis { } out } // interpret + + + class SimulatedStack { + private var types: List[InferredType] = Nil + private var depth = 0 + + /** Remove and return the topmost element on the stack. If the + * stack is empty, return a reference to a negative index on the + * stack, meaning it refers to elements pushed by a predecessor block. + */ + def pop: InferredType = types match { + case head :: rest => + types = rest + head + case _ => + depth -= 1 + TypeOfStackPos(depth) + } + + def pop2: (InferredType, InferredType) = { + (pop, pop) + } + + def push(t: InferredType) { + depth += 1 + types += t + } + + def push(k: TypeKind): Unit = push(Const(k)) + } + + abstract class InferredType { + /** Return the type kind pointed by this inferred type. */ + def getKind(in: lattice.Elem): icodes.TypeKind = this match { + case Const(k) => + k + case TypeOfVar(l: icodes.Local) => + if (in.vars.isDefinedAt(l)) in.vars(l) else l.kind + case TypeOfStackPos(n: Int) => + assert(in.stack.length >= n) + in.stack(n) + } + } + /** A type that does not depend on input to the transfer function. */ + case class Const(t: icodes.TypeKind) extends InferredType + /** The type of a given local variable. */ + case class TypeOfVar(l: icodes.Local) extends InferredType + /** The type found at a stack position. */ + case class TypeOfStackPos(n: Int) extends InferredType + + abstract class Gen + case class Bind(l: icodes.Local, t: InferredType) extends Gen + case class Push(t: InferredType) extends Gen + + /** A flow transfer function of a basic block. */ + class TransferFunction(consumed: Int, gens: List[Gen]) extends (lattice.Elem => lattice.Elem) { + def apply(in: lattice.Elem): lattice.Elem = { + val out = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) + val bindings = out.vars + val stack = out.stack + + out.stack.pop(consumed) + for (val g <- gens) g match { + case Bind(l, t) => + out.vars += (l -> t.getKind(in)) + case Push(t) => + stack.push(t.getKind(in)) + } + out + } + } + } + + class Timer { + var millis = 0L + + private var lastStart = 0L + + def reset { + millis = 0L + } + + def start { + lastStart = System.currentTimeMillis + } + + /** Stop the timer and return the number of milliseconds since the last + * call to start. The 'millis' field is increased by the elapsed time. + */ + def stop: Long = { + val elapsed = System.currentTimeMillis - lastStart + millis += elapsed + elapsed + } } } diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 5f4a444692..e497829889 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -288,7 +288,7 @@ abstract class Inliners extends SubComponent { if (m.code ne null) { if (settings.debug.value) log("Analyzing " + m + " count " + count); - tfa.init(m) + tfa.reinit(m) tfa.run for (bb <- linearizer.linearize(m)) { var info = tfa.in(bb); diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/ClassfileParser.scala b/src/compiler/scala/tools/nsc/symtab/classfile/ClassfileParser.scala index 3cf8b8f25a..6fdaec7caf 100644 --- a/src/compiler/scala/tools/nsc/symtab/classfile/ClassfileParser.scala +++ b/src/compiler/scala/tools/nsc/symtab/classfile/ClassfileParser.scala @@ -329,12 +329,9 @@ abstract class ClassfileParser { if ((sflags & DEFERRED) != 0) sflags = sflags & ~DEFERRED | ABSTRACT val c = pool.getClassSymbol(in.nextChar) if (c != clazz) { - assert(true) if ((clazz eq NoSymbol) && (c ne NoSymbol)) { // XXX: needed for build compiler, so can't protect with inIDE - assert(true) clazz = c } else if (inIDE) { - assert(true) Console.println("WRONG CLASS: expected: " + clazz + " found " + c) } else throw new IOException("class file '" + in.file + "' contains wrong " + c) } diff --git a/src/compiler/scala/tools/nsc/util/Statistics.scala b/src/compiler/scala/tools/nsc/util/Statistics.scala index 59ccbd81f9..a1a76f0c99 100644 --- a/src/compiler/scala/tools/nsc/util/Statistics.scala +++ b/src/compiler/scala/tools/nsc/util/Statistics.scala @@ -40,5 +40,6 @@ abstract class Statistics { inform("#norm other: " + analyzer.normO) inform("#subtype : " + subtypeCount) inform("ms subtype: " + subtypeMillis) + inform("ms type-flow-analysis: " + analysis.timer.millis) } } |