diff options
14 files changed, 608 insertions, 86 deletions
diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 7777a89cfa..23cb3dc9bb 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -26,6 +26,7 @@ import backend.icode.{ICodes, GenICode, Checkers}; import backend.ScalaPrimitives; import backend.jvm.GenJVM; import backend.opt.Inliners; +import backend.icode.analysis.TypeFlowAnalysis; class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable with Trees @@ -64,6 +65,10 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable val global: Global.this.type = Global.this } + object analysis extends TypeFlowAnalysis { + val global: Global.this.type = Global.this; + } + object checkers extends Checkers { val global: Global.this.type = Global.this } @@ -428,7 +433,7 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable globalPhase = globalPhase.next; if (settings.check contains globalPhase.name) { phase = globalPhase; - if (globalPhase.name == "jvm") icodeChecker.checkICodes; + if (globalPhase.id >= icodePhase.id) icodeChecker.checkICodes; else checker.checkTrees; } if (settings.statistics.value) statistics.print(phase); diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index 0c9d6dc2c3..59e3aa5d6d 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -10,6 +10,7 @@ package scala.tools.nsc.backend.icode; import scala.tools.nsc.ast._; import scala.collection.mutable.Map; import scala.tools.nsc.util.Position; +import scala.tools.nsc.backend.icode.analysis.ProgramPoint; trait BasicBlocks requires ICodes { import opcodes._; @@ -19,7 +20,9 @@ trait BasicBlocks requires ICodes { * either executed all, or none. No jumps * to/from the "middle" of the basic block are allowed. */ - class BasicBlock (theLabel: int, val code: Code) { + class BasicBlock (theLabel: int, val code: Code) + extends AnyRef + with ProgramPoint[BasicBlock] { /** The type stack at the begining of the block */ var initialStack : TypeStack = null; @@ -27,10 +30,6 @@ trait BasicBlocks requires ICodes { /** The label of the block */ val label = theLabel; - /** The substitute variables of the block - * in the case of a recursive method */ - var substituteVars : List[Symbol] = null; - /** The stack at the end of the block */ var endStack : TypeStack = null; @@ -49,6 +48,13 @@ trait BasicBlocks requires ICodes { private var closed: boolean = false; private var instrs: Array[Instruction] = _; + private var touched = false; + + def toList: List[Instruction] = { + if (closed && touched) + instructionList = List.fromArray(instrs); + instructionList + } // public: @@ -126,7 +132,7 @@ trait BasicBlocks requires ICodes { var i = 0; while (i < instrs.length) { map get instrs(i) match { - case Some(instr) => replaceInstruction(i, instr); + case Some(instr) => touched = replaceInstruction(i, instr); case None => (); } i = i + 1; @@ -163,6 +169,7 @@ trait BasicBlocks requires ICodes { assert (!closed || ignore, "BasicBlock closed"); if (!ignore) { + touched = true; instr.pos = pos; instructionList = instr :: instructionList; _lastInstruction = instr; @@ -180,13 +187,13 @@ trait BasicBlocks requires ICodes { def open = { closed = false; + ignore = false; } - def instructions: List[Instruction] = instructionList; - def clear: Unit = { instructionList = Nil; instrs = null; + preds = null; } def isEmpty: Boolean = instructionList.isEmpty; @@ -248,7 +255,7 @@ trait BasicBlocks requires ICodes { * in different code 'chunks' than the rest of the method. */ def predecessors: List[BasicBlock] = { - if (preds == null) +// if (preds == null) preds = code.blocks.elements.filter (p => (p.successors contains this)).toList; preds } diff --git a/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala b/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala index 0963a89bc9..9b03882889 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala @@ -189,10 +189,10 @@ abstract class Checkers { /** Checks that tpe is a subtype of one of the allowed types */ def checkType(tpe: TypeKind, allowed: TypeKind*) = - if (isOneOf(tpe, allowed: _*)) + if (isOneOf(tpe, allowed: _*) || tpe <:< CASE_CLASS) /* hack */ () else - error(tpe.toString() + " is not one of: " + allowed); + error(tpe.toString() + " is not one of: " + allowed.toList.mkString("{", ", ", "}")); /** Checks that the 2 topmost elements on stack are of the * kind TypeKind. @@ -313,16 +313,18 @@ abstract class Checkers { checkStack(1); val fieldType = toTypeKind(field.tpe); val actualType = stack.pop; - if (!(actualType <:< fieldType)) + if (!(actualType <:< fieldType) && + actualType != CASE_CLASS) typeError(fieldType, actualType); } else { checkStack(2); stack.pop2 match { case Pair(value, obj) => checkField(obj, field); - val fieldType = toTypeKind(field.tpe); - if (fieldType != SCALA_ALL_REF && !(value <:< fieldType)) - typeError(fieldType, value); + val fieldType = toTypeKind(field.tpe); + if (fieldType != SCALA_ALL_REF && !(value <:< fieldType) + && value != CASE_CLASS) + typeError(fieldType, value); } } @@ -561,30 +563,5 @@ abstract class Checkers { def isOneOf(k1: TypeKind, kinds: TypeKind*) = kinds.exists( k => k1 <:< k); - - /** - * Dummy TypeKind to represent the ConcatClass in a platform-independent - * way. For JVM it would have been a REFERENCE to 'StringBuffer'. - */ - case object ConcatClass extends TypeKind { - override def toString() = "ConcatClass"; - - /** - * Approximate `lub'. The common type of two references is - * always AnyRef. For 'real' least upper bound wrt to subclassing - * use method 'lub'. - */ - override def maxType(other: TypeKind): TypeKind = - other match { - case REFERENCE(_) => REFERENCE(definitions.AnyRefClass); - case _ => - abort("Uncomparbale type kinds: ConcatClass with " + other); - } - - /** Checks subtyping relationship. */ - override def <:<(other: TypeKind): Boolean = (this eq other); - - override def isReferenceType: Boolean = false; - } } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala index 03c9976437..a49eb80eef 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala @@ -49,6 +49,12 @@ abstract class ICodes extends AnyRef global.icodes.classes.values foreach { c => printer.printClass(c); } } + def dump(m: global.icodes.IMethod) = { + val printer = new global.icodePrinter.TextPrinter(new PrintWriter(System.out, true), + new global.icodes.DumpLinearizer()); + printer.printMethod(m); + } + def init = { } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala index 912358762c..2a1b301598 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala @@ -175,7 +175,8 @@ trait Opcodes requires ICodes { */ case class STORE_FIELD(field: Symbol, isStatic: boolean) extends Instruction { /** Returns a string representation of this instruction */ - override def toString(): String = "STORE_FIELD "+field.toString(); //+isStatic?" (static)":""; + override def toString(): String = + "STORE_FIELD "+field.toString() + (if (isStatic) " (static)" else " (dynamic)"); override def consumed = 2; override def produced = 0; @@ -441,6 +442,11 @@ trait Opcodes requires ICodes { case _ => false; } + def isSuper: Boolean = this match { + case SuperCall(_) => true + case _ => false + } + /** Is this an instance method call? */ def hasInstance: Boolean = this match { case Dynamic => true; diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala index 7dbb3e1313..bc0104ce78 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala @@ -114,13 +114,13 @@ abstract class Printers { def printBlock(bb: BasicBlock): Unit = { print(bb.label); print(": "); indent; println; - bb.instructions foreach printInstruction; + bb.toList foreach printInstruction; undent; println; } def printInstruction(i: Instruction): Unit = { - if (settings.debug.value) - print("/* " + Position.line(clazz.cunit.source, i.pos) + " */ "); +// if (settings.debug.value) +// print("/* " + Position.line(clazz.cunit.source, i.pos) + " */ "); println(i.toString()); } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala index ce2895c8c7..fc1048699b 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala @@ -216,6 +216,8 @@ trait TypeKinds requires ICodes { "REFERENCE to null class symbol."); assert(cls != definitions.ArrayClass, "REFERENCE to Array is not allowed, should be ARRAY[..] instead"); + assert(cls != NoSymbol, + "REFERENCE to NoSymbol not allowed!"); override def toString(): String = "REFERENCE(" + cls.fullNameString + ")"; @@ -291,6 +293,31 @@ trait TypeKinds requires ICodes { } + /** + * Dummy TypeKind to represent the ConcatClass in a platform-independent + * way. For JVM it would have been a REFERENCE to 'StringBuffer'. + */ + case object ConcatClass extends TypeKind { + override def toString() = "ConcatClass"; + + /** + * Approximate `lub'. The common type of two references is + * always AnyRef. For 'real' least upper bound wrt to subclassing + * use method 'lub'. + */ + override def maxType(other: TypeKind): TypeKind = + other match { + case REFERENCE(_) => REFERENCE(definitions.AnyRefClass); + case _ => + abort("Uncomparbale type kinds: ConcatClass with " + other); + } + + /** Checks subtyping relationship. */ + override def <:<(other: TypeKind): Boolean = (this eq other); + + override def isReferenceType: Boolean = false; + } + ////////////////// Conversions ////////////////////////////// diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala index 69f1f34cb7..7e520903ff 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala @@ -37,6 +37,8 @@ trait TypeStacks requires ICodes { if (t != UNIT) types = t :: types; + def head: TypeKind = types.head; + /** Removes the value on top of the stack, and returns it. It assumes * the stack contains at least one element. */ @@ -56,6 +58,9 @@ trait TypeStacks requires ICodes { */ def pop3: Triple[TypeKind, TypeKind, TypeKind] = Triple(pop, pop, pop); + /** Drop the first n elements of the stack. */ + def pop(n: Int): Unit = types = types.drop(n); + /** * A TypeStack aggress with another one if they have the same * length and each type kind agrees position-wise. Two @@ -83,9 +88,8 @@ trait TypeStacks requires ICodes { } /* This method returns a String representation of the stack */ - override def toString() = { - (types.foldLeft(new StringBuffer("")) ((buf, k) => buf.append(" ").append(k))).toString(); - } + override def toString() = types.mkString("<", ",", ">"); + override def equals(other: Any): Boolean = ( other.isInstanceOf[TypeStack] && diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala new file mode 100644 index 0000000000..6107e66645 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -0,0 +1,45 @@ +package scala.tools.nsc.backend.icode.analysis; + +import scala.collection.mutable.{Map, HashMap, Set, HashSet}; + +/** A generic framework for data flow analysis. + */ +trait DataFlowAnalysis[L <: CompleteLattice] { + /** A type for program points. */ + type P <: ProgramPoint[P]; + val lattice: L; + + val worklist: Set[P] = new HashSet; + + val in: Map[P, lattice.Elem] = new HashMap; + val out: Map[P, lattice.Elem] = new HashMap; + + /* Implement this function to initialize the worklist. */ + def init(f: => Unit): Unit = { + in.clear; out.clear; worklist.clear; + f; + } + + def run: Unit; + + /** Implement forward dataflow analysis: the transfer function is + * applied when inputs to a Program point change, to obtain the new + * output value. + */ + def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = { + while (!worklist.isEmpty) { + val point = worklist.elements.next; worklist -= point; + val output = f(point, in(point)); + + if (out(point) == (lattice.bottom) || output != out(point)) { + out(point) = output; + val succs = point.successors; + succs foreach { p => + if (!worklist.contains(p)) + worklist += p; + in(p) = lattice.lub(p.predecessors map out.apply) + } + } + } + } +} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/Lattice.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/Lattice.scala new file mode 100644 index 0000000000..9585c929dc --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/Lattice.scala @@ -0,0 +1,19 @@ +package scala.tools.nsc.backend.icode.analysis; + +/** A complete lattice. + */ +trait CompleteLattice { + type Elem; + + /** Return the least upper bound of `a' and `b' */ + def lub2(a: Elem, b: Elem): Elem; + + /** Return the top element. */ + def top: Elem; + + /** Return the bottom element. */ + def bottom: Elem; + + /** Compute the least upper bound of a list of elements. */ + def lub(xs: List[Elem]): Elem = xs reduceLeft lub2; +} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ProgramPoint.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ProgramPoint.scala new file mode 100644 index 0000000000..a1e68d6043 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/ProgramPoint.scala @@ -0,0 +1,10 @@ +package scala.tools.nsc.backend.icode.analysis; + +/** Program points are locations in the program where we want to + * assert certain properties through data flow analysis, e.g. + * basic blocks. + */ +trait ProgramPoint[a <: ProgramPoint[a]] { + def predecessors: List[a]; + def successors: List[a]; +} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala new file mode 100644 index 0000000000..c2e1169f0b --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -0,0 +1,304 @@ +package scala.tools.nsc.backend.icode.analysis; + +import scala.collection.mutable.{Map, HashMap}; + +/** A data-flow analysis on types, that works on ICode. + */ +abstract class TypeFlowAnalysis { + val global: Global; + import global._; + + /** The lattice of ICode types. + */ + object typeLattice extends CompleteLattice { + type Elem = icodes.TypeKind; + + val Object = icodes.REFERENCE(global.definitions.ObjectClass); + val All = icodes.REFERENCE(global.definitions.AllClass); + + def top = Object; + def bottom = All; + + def lub2(a: Elem, b: Elem) = + if (a eq bottom) b + else if (b eq bottom) a + else icodes.lub(a, b); + } + + /** The lattice of type stacks. It is a straight forward extension of + * the type lattice (lub is pairwise lub of the list elements). + */ + object typeStackLattice extends CompleteLattice { + import icodes._; + type Elem = TypeStack; + + override val top = new TypeStack; + override val bottom = new TypeStack; + + def lub2(s1: TypeStack, s2: TypeStack) = { + if (s1 eq bottom) s2 + else if (s2 eq bottom) s1 + else { + if (s1.length != s2.length) + throw new CheckerError("Incompatible stacks: " + s1 + " and " + s2); + new TypeStack(List.map2(s1.types, s2.types) (icodes.lub)) + } + } + } + + /** A map which returns the bottom type for unfound elements */ + class VarBinding extends 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); + } + + def this(o: VarBinding) = { + this(); + this ++= o + } + } + + /** The type flow lattice contains a binding from local variable + * names to types and a type stack. + */ + object typeFlowLattice extends CompleteLattice { + import icodes._; + type Elem = Pair[VarBinding, icodes.TypeStack]; + + override val top = new Pair(new VarBinding, typeStackLattice.top) { + override def equals(that: Any) = (this eq that.asInstanceOf[AnyRef]); + } + override val bottom = new Pair(new VarBinding, typeStackLattice.bottom) { + override def equals(that: Any) = (this eq that.asInstanceOf[AnyRef]); + } + + def lub2(a: Elem, b: Elem) = { + val Pair(env1, s1) = a; + val Pair(env2, s2) = b; + + val resultingLocals = new VarBinding; + + for (val binding1 <- env1.elements) { + val tp2 = env2(binding1._1); + resultingLocals += binding1._1 -> typeLattice.lub2(binding1._2, tp2); + } + + for (val binding2 <- env2.elements; resultingLocals(binding2._1) eq typeLattice.bottom) { + val tp1 = env1(binding2._1); + resultingLocals += binding2._1 -> typeLattice.lub2(binding2._2, tp1); + } + + Pair(resultingLocals, typeStackLattice.lub2(a._2, b._2)) + } + } + + class MethodTFA extends DataFlowAnalysis[typeFlowLattice.type] { + import icodes._; + import icodes.opcodes._; + + type P = BasicBlock; + val lattice = typeFlowLattice; + + val STRING = icodes.REFERENCE(TypeFlowAnalysis.this.global.definitions.StringClass); + var method: IMethod = _; + + def this(m: icodes.IMethod) = { + this(); + this.method = m; + init { + worklist += m.code.startBlock; + worklist ++= (m.exh map (.startBlock)); + m.code.blocks.foreach { b => + in(b) = typeFlowLattice.bottom; + out(b) = typeFlowLattice.bottom; + } + m.exh foreach { e => + val stack = new TypeStack; + stack.push( + REFERENCE(if (e.cls eq NoSymbol) definitions.ObjectClass else e.cls)); + in(e.startBlock) = Pair(in(e.startBlock)._1, stack); + } + } + } + + 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) + } + + /** Abstract interpretation for one instruction. */ + def interpret(in: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = { + val out = Pair(new VarBinding(in._1), new TypeStack(in._2)); + val bindings = out._1; + val stack = out._2; + +/* if (settings.debug.value) { + Console.println("Stack: " + stack); + Console.println(i); + } */ + i match { + + case THIS(clasz) => + stack push toTypeKind(clasz.tpe); + + case CONSTANT(const) => + stack push toTypeKind(const.tpe); + + case LOAD_ARRAY_ITEM(kind) => + val Pair(INT, ARRAY(elem)) = stack.pop2; + stack.push(elem); + + case LOAD_LOCAL(local, isArg) => + 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, isArg) => + val t = stack.pop; + bindings += local -> t; + + 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; + stack push kind; + + 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 NEW(kind) => + stack.push(kind); + + case CREATE_ARRAY(elem) => + stack.pop; + 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(where) => + () + + 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 _ => + dump; + abort("Unknown instruction: " + i); + + } + out + } + } +} diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index b60ab3055c..901745fa5c 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -45,13 +45,23 @@ abstract class Inliners extends SubComponent { */ class Inliner { + /* fresh name counter */ + var count = 0; + + def freshName(s: String) = { + val ret = s + this.count; + this.count = this.count + 1; + ret + } + def inline(caller: IMethod, block: BasicBlock, instr: Instruction, callee: IMethod): Unit = { - if (settings.debug.value) - log("Inlining " + callee + " in " + caller + " at pos: " + - classes(caller.symbol.owner).cunit.position(instr.pos)); + log("Inlining " + callee + " in " + caller + " at pos: " + + classes(caller.symbol.owner).cunit.position(instr.pos)); + + val a = new analysis.MethodTFA(callee); /* The exception handlers that are active at the current block. */ val activeHandlers = caller.exh.filter(.covered.contains(block)); @@ -59,17 +69,20 @@ abstract class Inliners extends SubComponent { /* Map 'original' blocks to the ones inlined in the caller. */ val inlinedBlock: Map[BasicBlock, BasicBlock] = new HashMap; - val instrBefore = block.instructions.takeWhile( i => i != instr); - val instrAfter = block.instructions.drop(instrBefore.length + 1); + val instrBefore = block.toList.takeWhile( i => i != instr); + val instrAfter = block.toList.drop(instrBefore.length + 1); - if (settings.debug.value) { - log("instrBefore: " + instrBefore); - log("instrAfter: " + instrAfter); - } assert(!instrAfter.isEmpty, "CALL_METHOD cannot be the last instrcution in block!"); // store the '$this' into the special local - val inlinedThis = new Local(caller.symbol.newVariable(instr.pos,"$inlThis"), REFERENCE(definitions.ObjectClass)); + val inlinedThis = new Local(caller.symbol.newVariable(instr.pos, freshName("$inlThis")), REFERENCE(definitions.ObjectClass)); + + /** buffer for the returned value */ + val retVal = + if (callee.returnType != UNIT) + new Local(caller.symbol.newVariable(instr.pos, freshName("$retVal")), callee.returnType); + else + null; /** Add a new block in the current context. */ def newBlock = { @@ -100,6 +113,9 @@ abstract class Inliners extends SubComponent { case CZJUMP(success, failure, cond, kind) => CZJUMP(inlinedBlock(success), inlinedBlock(failure), cond, kind); + case SWITCH(tags, labels) => + SWITCH(tags, labels map inlinedBlock); + case RETURN(kind) => JUMP(afterBlock); @@ -108,11 +124,15 @@ abstract class Inliners extends SubComponent { addLocals(caller, callee.locals); addLocal(caller, inlinedThis); + if (retVal ne null) + addLocal(caller, retVal); callee.code.blocks.foreach { b => - if (b != callee.code.startBlock) - inlinedBlock += b -> newBlock; + inlinedBlock += b -> newBlock; } + // analyse callee + a.run; + // re-emit the instructions before the call block.open; block.clear; @@ -124,27 +144,45 @@ abstract class Inliners extends SubComponent { } block.emit(STORE_LOCAL(inlinedThis, false)); - // inline the start block of the callee - callee.code.startBlock.traverse { i => - block.emit(map(i), 0); - } + // jump to the start block of the callee + block.emit(JUMP(inlinedBlock(callee.code.startBlock))); block.close; // duplicate the other blocks in the callee - callee.code.traverse { bb => - if (bb != callee.code.startBlock) { - bb.traverse( i => inlinedBlock(bb).emit(map(i), 0) ); - inlinedBlock(bb).close; + linearizer.linearize(callee).foreach { bb => + var info = a.in(bb); + bb traverse { i => + i match { + case RETURN(kind) => kind match { + case UNIT => + if (!info._2.types.isEmpty) { + log("** Dumping useless stack elements"); + info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t)); } + } + case _ => + if (info._2.length > 1) { + log("** Dumping useless stack elements"); + inlinedBlock(bb).emit(STORE_LOCAL(retVal, false)); + info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t)); } + inlinedBlock(bb).emit(LOAD_LOCAL(retVal, false)); + } + } + case _ => (); + } + inlinedBlock(bb).emit(map(i), 0); + info = a.interpret(info, i); } + inlinedBlock(bb).close; } instrAfter.foreach(afterBlock.emit); afterBlock.close; + count = count + 1; } - /** Add a local to this method, performing alfa-renaming - * if necessary. + /** Add a local to this method, alfa-renaming is not + * necessary because we use symbols to refer to locals. */ def addLocals(m: IMethod, ls: List[Local]): Unit = { m.locals = m.locals ::: ls; @@ -153,38 +191,112 @@ abstract class Inliners extends SubComponent { def addLocal(m: IMethod, l: Local): Unit = m.locals = m.locals ::: List(l); - val InlineAttr = if (settings.inline.value) global.definitions.getClass("scala.inline").tpe; + val InlineAttr = if (settings.inline.value) global.definitions.getClass("scala.inline").tpe else null; def analyzeClass(cls: IClass): Unit = if (settings.inline.value) { + log("Analyzing " + cls); cls.methods.foreach { m => analyzeMethod(m) }} - def analyzeMethod(m: IMethod): Unit = { + def analyzeMethod(m: IMethod): Unit = try { var retry = false; var count = 0; do { retry = false; - if (m.code ne null) - m.code.traverse { bb => + if (m.code ne null) { + this.count = 0; + if (settings.debug.value) + log("Analyzing " + m + " count " + count); + val a = new analysis.MethodTFA(m); + a.run; + linearizer.linearize(m).foreach { bb => + var info = a.in(bb); bb.traverse { i => - if (!retry) + if (!retry) { i match { - case CALL_METHOD(msym, _) => - if (definitions.isFunctionType(msym.owner.tpe) - || msym.attributes.exists(a => a._1 == InlineAttr)) - classes(msym.owner).lookupMethod(msym.name) match { + case CALL_METHOD(msym, Dynamic) => + val receiver = info._2.types.drop(msym.info.paramTypes.length).head match { + case REFERENCE(s) => s; + case _ => NoSymbol; + } + var concreteMethod = msym; + if (receiver != msym.owner && receiver != NoSymbol) { + concreteMethod = msym.overridingSymbol(receiver); + log("" + i + " has actual receiver: " + receiver); + } + + if ( classes.contains(receiver) + && (isClosureClass(receiver) + || concreteMethod.isFinal + || msym.attributes.exists(a => a._1 == InlineAttr))) { + classes(receiver).lookupMethod(concreteMethod) match { case Some(inc) => - retry = true; - count = count + 1; - inline(m, bb, i, inc); + if (inc != m && (inc.code ne null) + && isSafeToInline(m, inc, info._2)) { + retry = true; + count = count + 1; + inline(m, bb, i, inc); + } case None => log("Couldn't find " + msym.name); } + } + case _ => (); - }}} + } + info = a.interpret(info, i); + }}}} } while (retry && count < 5); + } catch { + case e => + Console.println("############# Cought exception: " + e + " #################"); + e.printStackTrace(); + dump(m); + throw e; } - } -} + + def isClosureClass(cls: Symbol): Boolean = { + val res = + cls.isFinal && + cls.tpe.parents.exists { t => + val TypeRef(_, sym, _) = t; + definitions.FunctionClass exists sym.== + } + Console.println("isClosureClass: " + cls + " is: " + res); + res + } + + + /** A method is safe to inline when: + * - it does not contain calls to private methods when + * called from another class + * - it is not inlined into a position with non-empty stack, + * while having a top-level finalizer (see liftedTry problem) + */ + def isSafeToInline(caller: IMethod, callee: IMethod, stack: TypeStack): Boolean = { + if (caller.symbol.owner != callee.symbol.owner) { + var callsPrivateMember = false; + for (val b <- callee.code.blocks) + for (val i <- b.toList) + i match { + case CALL_METHOD(m, style) => + if (m.hasFlag(Flags.PRIVATE) || style.isSuper) + callsPrivateMember = true; + case LOAD_FIELD(f, _) => + if (f.hasFlag(Flags.PRIVATE)) callsPrivateMember = true; + case _ => () + } + if (callsPrivateMember) return false; + } + + if (stack.length > (1 + callee.symbol.info.paramTypes.length) && + (callee.exh exists (.covered.contains(callee.code.startBlock)))) + false; + else + true + } + + } /* class Inliner */ +} /* class Inliners */ diff --git a/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala b/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala index f72fe2d266..74729101e0 100644 --- a/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala +++ b/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala @@ -214,7 +214,7 @@ trait ICodeToDCode requires DCode { } } } - val Pair(ins, outStack) = convLoop(icblk.instructions, startStack) + val Pair(ins, outStack) = convLoop(icblk.toList, startStack) tripblk.instrs = ins outStack } |