diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/backend/icode')
22 files changed, 0 insertions, 7718 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala deleted file mode 100644 index ad1975ef23..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ /dev/null @@ -1,553 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -import scala.collection.{ mutable, immutable } -import mutable.ListBuffer -import backend.icode.analysis.ProgramPoint -import scala.language.postfixOps - -trait BasicBlocks { - self: ICodes => - - import opcodes._ - import global._ - - /** Override Array creation for efficiency (to not go through reflection). */ - private implicit val instructionTag: scala.reflect.ClassTag[Instruction] = new scala.reflect.ClassTag[Instruction] { - def runtimeClass: java.lang.Class[Instruction] = classOf[Instruction] - final override def newArray(len: Int): Array[Instruction] = new Array[Instruction](len) - } - - object NoBasicBlock extends BasicBlock(-1, null) - - /** This class represents a basic block. Each - * basic block contains a list of instructions that are - * either executed all, or none. No jumps - * to/from the "middle" of the basic block are allowed (modulo exceptions). - */ - class BasicBlock(val label: Int, val method: IMethod) extends ProgramPoint[BasicBlock] { - outer => - - import BBFlags._ - - def code = if (method eq null) NoCode else method.code - - private final class SuccessorList() { - private var successors: List[BasicBlock] = Nil - /** This method is very hot! Handle with care. */ - private def updateConserve() { - var lb: ListBuffer[BasicBlock] = null - var matches = 0 - var remaining = successors - val direct = directSuccessors - var scratchHandlers: List[ExceptionHandler] = method.exh - var scratchBlocks: List[BasicBlock] = direct - - def addBlock(bb: BasicBlock) { - if (matches < 0) - lb += bb - else if (remaining.isEmpty || bb != remaining.head) { - lb = ListBuffer[BasicBlock]() ++= (successors take matches) += bb - matches = -1 - } - else { - matches += 1 - remaining = remaining.tail - } - } - - while (scratchBlocks ne Nil) { - addBlock(scratchBlocks.head) - scratchBlocks = scratchBlocks.tail - } - /* Return a list of successors for 'b' that come from exception handlers - * covering b's (non-exceptional) successors. These exception handlers - * might not cover 'b' itself. This situation corresponds to an - * exception being thrown as the first thing of one of b's successors. - */ - while (scratchHandlers ne Nil) { - val handler = scratchHandlers.head - if (handler covers outer) - addBlock(handler.startBlock) - - scratchBlocks = direct - while (scratchBlocks ne Nil) { - if (handler covers scratchBlocks.head) - addBlock(handler.startBlock) - scratchBlocks = scratchBlocks.tail - } - scratchHandlers = scratchHandlers.tail - } - // Blocks did not align: create a new list. - if (matches < 0) - successors = lb.toList - // Blocks aligned, but more blocks remain. Take a prefix of the list. - else if (remaining.nonEmpty) - successors = successors take matches - // Otherwise the list is unchanged, leave it alone. - } - - /** This is called millions of times: it is performance sensitive. */ - def updateSuccs() { - if (isEmpty) { - if (successors.nonEmpty) - successors = Nil - } - else updateConserve() - } - def toList = successors - } - - /** Flags of this basic block. */ - private[this] var flags: Int = 0 - - /** Does this block have the given flag? */ - def hasFlag(flag: Int): Boolean = (flags & flag) != 0 - - /** Set the given flag. */ - private def setFlag(flag: Int): Unit = flags |= flag - private def resetFlag(flag: Int) { - flags &= ~flag - } - - /** Is this block closed? */ - def closed: Boolean = hasFlag(CLOSED) - def closed_=(b: Boolean) = if (b) setFlag(CLOSED) else resetFlag(CLOSED) - - /** When set, the `emit` methods will be ignored. */ - def ignore: Boolean = hasFlag(IGNORING) - def ignore_=(b: Boolean) = if (b) setFlag(IGNORING) else resetFlag(IGNORING) - - /** Is this block the head of a while? */ - def loopHeader = hasFlag(LOOP_HEADER) - def loopHeader_=(b: Boolean) = - if (b) setFlag(LOOP_HEADER) else resetFlag(LOOP_HEADER) - - /** Is this block the start block of an exception handler? */ - def exceptionHandlerStart = hasFlag(EX_HEADER) - def exceptionHandlerStart_=(b: Boolean) = - if (b) setFlag(EX_HEADER) else resetFlag(EX_HEADER) - - /** Has this basic block been modified since the last call to 'successors'? */ - def touched = hasFlag(DIRTYSUCCS) - def touched_=(b: Boolean) = if (b) { - setFlag(DIRTYSUCCS | DIRTYPREDS) - } else { - resetFlag(DIRTYSUCCS | DIRTYPREDS) - } - - // basic blocks start in a dirty state - setFlag(DIRTYSUCCS | DIRTYPREDS) - - /** Cached predecessors. */ - var preds: List[BasicBlock] = Nil - - /** Local variables that are in scope at entry of this basic block. Used - * for debugging information. - */ - val varsInScope: mutable.Set[Local] = new mutable.LinkedHashSet() - - /** ICode instructions, used as temporary storage while emitting code. - * Once closed is called, only the `instrs` array should be used. - */ - private var instructionList: List[Instruction] = Nil - private var instrs: Array[Instruction] = _ - - def take(n: Int): Seq[Instruction] = - if (closed) instrs take n else instructionList takeRight n reverse - - def toList: List[Instruction] = - if (closed) instrs.toList else instructionList.reverse - - /** Return an iterator over the instructions in this basic block. */ - def iterator: Iterator[Instruction] = - if (closed) instrs.iterator else instructionList.reverseIterator - - /** return the underlying array of instructions */ - def getArray: Array[Instruction] = { - assert(closed, this) - instrs - } - - def fromList(is: List[Instruction]) { - code.touched = true - instrs = is.toArray - closed = true - } - - /** Return the index of inst. Uses reference equality. - * Returns -1 if not found. - */ - def indexOf(inst: Instruction): Int = { - assert(closed, this) - instrs indexWhere (_ eq inst) - } - - /** Apply a function to all the instructions of the block. */ - final def foreach[U](f: Instruction => U) = { - if (!closed) dumpMethodAndAbort(method, this) - else instrs foreach f - - // !!! If I replace "instrs foreach f" with the following: - // var i = 0 - // val len = instrs.length - // while (i < len) { - // f(instrs(i)) - // i += 1 - // } - // - // Then when compiling under -optimise, quick.plugins fails as follows: - // - // quick.plugins: - // [mkdir] Created dir: /scratch/trunk6/build/quick/classes/continuations-plugin - // [scalacfork] Compiling 5 files to /scratch/trunk6/build/quick/classes/continuations-plugin - // [scalacfork] error: java.lang.VerifyError: (class: scala/tools/nsc/typechecker/Implicits$ImplicitSearch, method: typedImplicit0 signature: (Lscala/tools/nsc/typechecker/Implicits$ImplicitInfo;Z)Lscala/tools/nsc/typechecker/Implicits$SearchResult;) Incompatible object argument for function call - // [scalacfork] at scala.tools.nsc.typechecker.Implicits$class.inferImplicit(Implicits.scala:67) - // [scalacfork] at scala.tools.nsc.Global$$anon$1.inferImplicit(Global.scala:419) - // [scalacfork] at scala.tools.nsc.typechecker.Typers$Typer.wrapImplicit$1(Typers.scala:170) - // [scalacfork] at scala.tools.nsc.typechecker.Typers$Typer.inferView(Typers.scala:174) - // [scalacfork] at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:963) - // [scalacfork] at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4378) - // - // This is bad and should be understood/eliminated. - } - - /** The number of instructions in this basic block so far. */ - def length = if (closed) instrs.length else instructionList.length - def size = length - - /** Return the n-th instruction. */ - def apply(n: Int): Instruction = - if (closed) instrs(n) else instructionList.reverse(n) - - ///////////////////// Substitutions /////////////////////// - - /** - * Replace the instruction at the given position. Used by labels when they are anchored. - * The replacing instruction is given the nsc.util.Position of the instruction it replaces. - */ - def replaceInstruction(pos: Int, instr: Instruction): Boolean = { - assert(closed, "Instructions can be replaced only after the basic block is closed") - instr.setPos(instrs(pos).pos) - instrs(pos) = instr - code.touched = true - true - } - - /** - * Replace the given instruction with the new one. - * Returns `true` if it actually changed something. - * The replacing instruction is given the nsc.util.Position of the instruction it replaces. - */ - def replaceInstruction(oldInstr: Instruction, newInstr: Instruction): Boolean = { - assert(closed, "Instructions can be replaced only after the basic block is closed") - - indexOf(oldInstr) match { - case -1 => false - case idx => - newInstr setPos oldInstr.pos - instrs(idx) = newInstr - code.touched = true - true - } - } - - /** Replaces `oldInstr` with `is`. It does not update - * the position field in the newly inserted instructions, so it behaves - * differently than the one-instruction versions of this function. - */ - def replaceInstruction(oldInstr: Instruction, is: List[Instruction]): Boolean = { - assert(closed, "Instructions can be replaced only after the basic block is closed") - - indexOf(oldInstr) match { - case -1 => false - case idx => - instrs = instrs.patch(idx, is, 1) - code.touched = true - true - } - } - - /** Removes instructions found at the given positions. - */ - def removeInstructionsAt(positions: Int*) { - assert(closed, this) - instrs = instrs.indices.toArray filterNot positions.toSet map instrs - code.touched = true - } - - /** Remove the last instruction of this basic block. It is - * fast for an open block, but slower when the block is closed. - */ - def removeLastInstruction() { - if (closed) - removeInstructionsAt(length) - else { - instructionList = instructionList.tail - code.touched = true - } - } - - /** Replaces all instructions found in the map. - */ - def subst(map: Map[Instruction, Instruction]): Unit = - if (!closed) - instructionList = instructionList map (x => map.getOrElse(x, x)) - else - instrs.iterator.zipWithIndex foreach { - case (oldInstr, i) => - if (map contains oldInstr) { - // SI-6288 clone important here because `replaceInstruction` assigns - // a position to `newInstr`. Without this, a single instruction can - // be added twice, and the position last position assigned clobbers - // all previous positions in other usages. - val newInstr = map(oldInstr).clone() - code.touched |= replaceInstruction(i, newInstr) - } - } - - ////////////////////// Emit ////////////////////// - - - /** Add a new instruction at the end of the block, - * using the same source position as the last emitted instruction - */ - def emit(instr: Instruction) { - val pos = if (instructionList.isEmpty) NoPosition else instructionList.head.pos - emit(instr, pos) - } - - /** Emitting does not set touched to true. During code generation this is a hotspot and - * setting the flag for each emit is a waste. Caching should happen only after a block - * is closed, which sets the DIRTYSUCCS flag. - */ - def emit(instr: Instruction, pos: Position) { - assert(!closed || ignore, this) - - if (ignore) { - if (settings.debug) { - /* Trying to pin down what it's likely to see after a block has been - * put into ignore mode so we hear about it if there's a problem. - */ - instr match { - case JUMP(_) | RETURN(_) | THROW(_) | SCOPE_EXIT(_) => // ok - case STORE_LOCAL(local) if nme.isExceptionResultName(local.sym.name) => // ok - case x => log("Ignoring instruction, possibly at our peril, at " + pos + ": " + x) - } - } - } - else { - instr.setPos(pos) - instructionList ::= instr - } - } - - def emit(is: Seq[Instruction]) { - is foreach (i => emit(i, i.pos)) - } - - /** The semantics of this are a little odd but it's designed to work - * seamlessly with the existing code. It emits each supplied instruction, - * then closes the block. The odd part is that if the instruction has - * pos == NoPosition, it calls the 1-arg emit, but otherwise it calls - * the 2-arg emit. This way I could retain existing behavior exactly by - * calling setPos on any instruction using the two arg version which - * I wanted to include in a call to emitOnly. - */ - def emitOnly(is: Instruction*) { - is foreach (i => if (i.pos == NoPosition) emit(i) else emit(i, i.pos)) - this.close() - } - - /** do nothing if block is already closed */ - def closeWith(instr: Instruction) { - if (!closed) { - emit(instr) - close() - } - } - - def closeWith(instr: Instruction, pos: Position) { - if (!closed) { - emit(instr, pos) - close() - } - } - - /** Close the block */ - def close() { - assert(!closed || ignore, this) - if (ignore && closed) { // redundant `ignore &&` for clarity -- we should never be in state `!ignore && closed` - // not doing anything to this block is important... - // because the else branch reverses innocent blocks, which is wrong when they're in ignore mode (and closed) - // reversing the instructions when (closed && ignore) wreaks havoc for nested label jumps (see comments in genLoad) - } else { - closed = true - setFlag(DIRTYSUCCS) - instructionList = instructionList.reverse - instrs = instructionList.toArray - if (instructionList.isEmpty) { - debuglog(s"Removing empty block $this") - code removeBlock this - } - } - } - - /** - * if cond is true, closes this block, entersIgnoreMode, and removes the block from - * its list of blocks. Used to allow a block to be started and then cancelled when it - * is discovered to be unreachable. - */ - def killIf(cond: Boolean) { - if (!settings.YdisableUnreachablePrevention && cond) { - debuglog(s"Killing block $this") - assert(instructionList.isEmpty, s"Killing a non empty block $this") - // only checked under debug because fetching predecessor list is moderately expensive - if (settings.debug) - assert(predecessors.isEmpty, s"Killing block $this which is referred to from ${predecessors.mkString}") - - close() - enterIgnoreMode() - } - } - - /** - * Same as killIf but with the logic of the condition reversed - */ - def killUnless(cond: Boolean) { - this killIf !cond - } - - def open() { - assert(closed, this) - closed = false - ignore = false - touched = true - instructionList = instructionList.reverse // prepare for appending to the head - } - - def clear() { - instructionList = Nil - instrs = null - preds = Nil - } - - final def isEmpty = instructionList.isEmpty - final def nonEmpty = !isEmpty - - /** Enter ignore mode: new 'emit'ted instructions will not be - * added to this basic block. It makes the generation of THROW - * and RETURNs easier. - */ - def enterIgnoreMode() = { - ignore = true - } - - /** Return the last instruction of this basic block. */ - def lastInstruction = - if (closed) instrs(instrs.length - 1) - else instructionList.head - - def exceptionSuccessors: List[BasicBlock] = - exceptionSuccessorsForBlock(this) - - def exceptionSuccessorsForBlock(block: BasicBlock): List[BasicBlock] = - method.exh collect { case x if x covers block => x.startBlock } - - /** Cached value of successors. Must be recomputed whenever a block in the current method is changed. */ - private val succs = new SuccessorList - - def successors: List[BasicBlock] = { - if (touched) { - succs.updateSuccs() - resetFlag(DIRTYSUCCS) - } - succs.toList - } - - def directSuccessors: List[BasicBlock] = - if (isEmpty) Nil else lastInstruction match { - case JUMP(whereto) => whereto :: Nil - case CJUMP(succ, fail, _, _) => fail :: succ :: Nil - case CZJUMP(succ, fail, _, _) => fail :: succ :: Nil - case SWITCH(_, labels) => labels - case RETURN(_) => Nil - case THROW(_) => Nil - case _ => - if (closed) - devWarning(s"$lastInstruction/${lastInstruction.getClass.getName} is not a control flow instruction") - - Nil - } - - /** Returns the predecessors of this block. */ - def predecessors: List[BasicBlock] = { - if (hasFlag(DIRTYPREDS)) { - resetFlag(DIRTYPREDS) - preds = code.blocks.iterator filter (_.successors contains this) toList - } - preds - } - - override def equals(other: Any): Boolean = other match { - case that: BasicBlock => (that.label == label) && (that.code == code) - case _ => false - } - - override def hashCode = label * 41 + code.hashCode - - private def succString = if (successors.isEmpty) "[S: N/A]" else successors.distinct.mkString("[S: ", ", ", "]") - private def predString = if (predecessors.isEmpty) "[P: N/A]" else predecessors.distinct.mkString("[P: ", ", ", "]") - - override def toString(): String = "" + label - - def blockContents = { - def posStr(p: Position) = if (p.isDefined) p.line.toString else "<??>" - val xs = this.toList map (instr => posStr(instr.pos) + "\t" + instr) - xs.mkString(fullString + " {\n ", "\n ", "\n}") - } - def predContents = predecessors.map(_.blockContents).mkString(predecessors.size + " preds:\n", "\n", "\n") - def succContents = successors.map(_.blockContents).mkString(successors.size + " succs:\n", "\n", "\n") - - def fullString: String = List("Block", label, succString, predString, flagsString) mkString " " - def flagsString: String = BBFlags.flagsToString(flags) - } -} - -object BBFlags { - /** This block is a loop header (was translated from a while). */ - final val LOOP_HEADER = (1 << 0) - - /** Ignoring mode: emit instructions are dropped. */ - final val IGNORING = (1 << 1) - - /** This block is the header of an exception handler. */ - final val EX_HEADER = (1 << 2) - - /** This block is closed. No new instructions can be added. */ - final val CLOSED = (1 << 3) - - /** Code has been changed, recompute successors. */ - final val DIRTYSUCCS = (1 << 4) - - /** Code has been changed, recompute predecessors. */ - final val DIRTYPREDS = (1 << 5) - - val flagMap = Map[Int, String]( - LOOP_HEADER -> "loopheader", - IGNORING -> "ignore", - EX_HEADER -> "exheader", - CLOSED -> "closed", - DIRTYSUCCS -> "dirtysuccs", - DIRTYPREDS -> "dirtypreds" - ) - def flagsToString(flags: Int) = { - flagMap collect { case (bit, name) if (bit & flags) != 0 => "<" + name + ">" } mkString " " - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/CheckerException.scala b/src/compiler/scala/tools/nsc/backend/icode/CheckerException.scala deleted file mode 100644 index 8bcdb6dbd2..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/CheckerException.scala +++ /dev/null @@ -1,10 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -class CheckerException(s: String) extends Exception(s) diff --git a/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala b/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala deleted file mode 100644 index 7243264773..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala +++ /dev/null @@ -1,71 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -import scala.collection.immutable - -/** - * Exception handlers are pieces of code that `handle` exceptions on - * the covered basic blocks. Since Scala's exception handling uses - * pattern matching instead of just class names to identify handlers, - * all our handlers will catch `Throwable` and rely on proper ordering - * in the generated code to preserve nesting. - */ -trait ExceptionHandlers { - self: ICodes => - - import global._ - import definitions.{ ThrowableClass } - - class ExceptionHandler(val method: IMethod, val label: TermName, val cls: Symbol, val pos: Position) { - def loadExceptionClass = if (cls == NoSymbol) ThrowableClass else cls - private var _startBlock: BasicBlock = _ - var finalizer: Finalizer = _ - - def setStartBlock(b: BasicBlock) = { - _startBlock = b - b.exceptionHandlerStart = true - } - def startBlock = _startBlock - - /** The list of blocks that are covered by this exception handler */ - var covered: immutable.Set[BasicBlock] = immutable.HashSet.empty[BasicBlock] - - def addCoveredBlock(b: BasicBlock): this.type = { - covered = covered + b - this - } - - /** Is `b` covered by this exception handler? */ - def covers(b: BasicBlock): Boolean = covered(b) - - /** The body of this exception handler. May contain 'dead' blocks (which will not - * make it into generated code because linearizers may not include them) */ - var blocks: List[BasicBlock] = Nil - - def addBlock(b: BasicBlock): Unit = blocks = b :: blocks - - override def toString() = "exh_" + label + "(" + cls.simpleName + ")" - - /** A standard copy constructor */ - def this(other: ExceptionHandler) = { - this(other.method, other.label, other.cls, other.pos) - - covered = other.covered - setStartBlock(other.startBlock) - finalizer = other.finalizer - } - - def dup: ExceptionHandler = new ExceptionHandler(this) - } - - class Finalizer(method: IMethod, label: TermName, pos: Position) extends ExceptionHandler(method, label, NoSymbol, pos) { - override def toString() = "finalizer_" + label - override def dup: Finalizer = new Finalizer(method, label, pos) - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala deleted file mode 100644 index b6f9bcc9ab..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala +++ /dev/null @@ -1,2239 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala -package tools.nsc -package backend -package icode - -import scala.collection.{ mutable, immutable } -import scala.collection.mutable.{ ListBuffer, Buffer } -import scala.tools.nsc.symtab._ -import scala.annotation.switch - -/** - * @author Iulian Dragos - * @version 1.0 - */ -abstract class GenICode extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - import definitions._ - import scalaPrimitives.{ - isArrayOp, isComparisonOp, isLogicalOp, - isUniversalEqualityOp, isReferenceEqualityOp - } - import platform.isMaybeBoxed - - private val bCodeICodeCommon: jvm.BCodeICodeCommon[global.type] = new jvm.BCodeICodeCommon(global) - import bCodeICodeCommon._ - - val phaseName = "icode" - - override def newPhase(prev: Phase) = new ICodePhase(prev) - - @inline private def debugassert(cond: => Boolean, msg: => Any) { - if (settings.debug) - assert(cond, msg) - } - - class ICodePhase(prev: Phase) extends StdPhase(prev) { - - override def description = "Generate ICode from the AST" - - var unit: CompilationUnit = NoCompilationUnit - - override def run() { - if (!settings.isBCodeActive) { - scalaPrimitives.init() - classes.clear() - } - super.run() - } - - override def apply(unit: CompilationUnit): Unit = { - if (settings.isBCodeActive) { return } - this.unit = unit - unit.icode.clear() - informProgress("Generating icode for " + unit) - gen(unit.body) - this.unit = NoCompilationUnit - } - - def gen(tree: Tree): Context = gen(tree, new Context()) - - def gen(trees: List[Tree], ctx: Context): Context = { - var ctx1 = ctx - for (t <- trees) ctx1 = gen(t, ctx1) - ctx1 - } - - /** If the selector type has a member with the right name, - * it is the host class; otherwise the symbol's owner. - */ - def findHostClass(selector: Type, sym: Symbol) = selector member sym.name match { - case NoSymbol => debuglog(s"Rejecting $selector as host class for $sym") ; sym.owner - case _ => selector.typeSymbol - } - - /////////////////// Code generation /////////////////////// - - def gen(tree: Tree, ctx: Context): Context = tree match { - case EmptyTree => ctx - - case PackageDef(pid, stats) => - gen(stats, ctx setPackage pid.name) - - case ClassDef(mods, name, _, impl) => - debuglog("Generating class: " + tree.symbol.fullName) - val outerClass = ctx.clazz - ctx setClass (new IClass(tree.symbol) setCompilationUnit unit) - addClassFields(ctx, tree.symbol) - classes += (tree.symbol -> ctx.clazz) - unit.icode += ctx.clazz - gen(impl, ctx) - ctx.clazz.methods = ctx.clazz.methods.reverse // preserve textual order - ctx.clazz.fields = ctx.clazz.fields.reverse // preserve textual order - ctx setClass outerClass - - // !! modules should be eliminated by refcheck... or not? - case ModuleDef(mods, name, impl) => - abort("Modules should not reach backend! " + tree) - - case ValDef(mods, name, tpt, rhs) => - ctx // we use the symbol to add fields - - case DefDef(mods, name, tparams, vparamss, tpt, rhs) => - debuglog("Entering method " + name) - val m = new IMethod(tree.symbol) - m.sourceFile = unit.source - m.returnType = if (tree.symbol.isConstructor) UNIT - else toTypeKind(tree.symbol.info.resultType) - ctx.clazz.addMethod(m) - - var ctx1 = ctx.enterMethod(m, tree.asInstanceOf[DefDef]) - addMethodParams(ctx1, vparamss) - m.native = m.symbol.hasAnnotation(definitions.NativeAttr) - - if (!m.isAbstractMethod && !m.native) { - ctx1 = genLoad(rhs, ctx1, m.returnType) - - // reverse the order of the local variables, to match the source-order - m.locals = m.locals.reverse - - rhs match { - case Block(_, Return(_)) => () - case Return(_) => () - case EmptyTree => - globalError("Concrete method has no definition: " + tree + ( - if (settings.debug) "(found: " + m.symbol.owner.info.decls.toList.mkString(", ") + ")" - else "") - ) - case _ => if (ctx1.bb.isEmpty) - ctx1.bb.closeWith(RETURN(m.returnType), rhs.pos) - else - ctx1.bb.closeWith(RETURN(m.returnType)) - } - if (!ctx1.bb.closed) ctx1.bb.close() - prune(ctx1.method) - } else - ctx1.method.setCode(NoCode) - ctx1 - - case Template(_, _, body) => - gen(body, ctx) - - case _ => - abort("Illegal tree in gen: " + tree) - } - - private def genStat(trees: List[Tree], ctx: Context): Context = - trees.foldLeft(ctx)((currentCtx, t) => genStat(t, currentCtx)) - - /** - * Generate code for the given tree. The trees should contain statements - * and not produce any value. Use genLoad for expressions which leave - * a value on top of the stack. - * - * @return a new context. This is necessary for control flow instructions - * which may change the current basic block. - */ - private def genStat(tree: Tree, ctx: Context): Context = tree match { - case Assign(lhs @ Select(_, _), rhs) => - val isStatic = lhs.symbol.isStaticMember - var ctx1 = if (isStatic) ctx else genLoadQualifier(lhs, ctx) - - ctx1 = genLoad(rhs, ctx1, toTypeKind(lhs.symbol.info)) - ctx1.bb.emit(STORE_FIELD(lhs.symbol, isStatic), tree.pos) - ctx1 - - case Assign(lhs, rhs) => - val ctx1 = genLoad(rhs, ctx, toTypeKind(lhs.symbol.info)) - val Some(l) = ctx.method.lookupLocal(lhs.symbol) - ctx1.bb.emit(STORE_LOCAL(l), tree.pos) - ctx1 - - case _ => - genLoad(tree, ctx, UNIT) - } - - private def genThrow(expr: Tree, ctx: Context): (Context, TypeKind) = { - require(expr.tpe <:< ThrowableTpe, expr.tpe) - - val thrownKind = toTypeKind(expr.tpe) - val ctx1 = genLoad(expr, ctx, thrownKind) - ctx1.bb.emit(THROW(expr.tpe.typeSymbol), expr.pos) - ctx1.bb.enterIgnoreMode() - - (ctx1, NothingReference) - } - - /** - * Generate code for primitive arithmetic operations. - * Returns (Context, Generated Type) - */ - private def genArithmeticOp(tree: Tree, ctx: Context, code: Int): (Context, TypeKind) = { - val Apply(fun @ Select(larg, _), args) = tree - var ctx1 = ctx - var resKind = toTypeKind(larg.tpe) - - debugassert(args.length <= 1, - "Too many arguments for primitive function: " + fun.symbol) - debugassert(resKind.isNumericType | resKind == BOOL, - resKind.toString() + " is not a numeric or boolean type " + - "[operation: " + fun.symbol + "]") - - args match { - // unary operation - case Nil => - ctx1 = genLoad(larg, ctx1, resKind) - code match { - case scalaPrimitives.POS => - () // nothing - case scalaPrimitives.NEG => - ctx1.bb.emit(CALL_PRIMITIVE(Negation(resKind)), larg.pos) - case scalaPrimitives.NOT => - ctx1.bb.emit(CALL_PRIMITIVE(Arithmetic(NOT, resKind)), larg.pos) - case _ => - abort("Unknown unary operation: " + fun.symbol.fullName + - " code: " + code) - } - - // binary operation - case rarg :: Nil => - resKind = getMaxType(larg.tpe :: rarg.tpe :: Nil) - if (scalaPrimitives.isShiftOp(code) || scalaPrimitives.isBitwiseOp(code)) - assert(resKind.isIntegralType | resKind == BOOL, - resKind.toString() + " incompatible with arithmetic modulo operation: " + ctx1) - - ctx1 = genLoad(larg, ctx1, resKind) - ctx1 = genLoad(rarg, - ctx1, // check .NET size of shift arguments! - if (scalaPrimitives.isShiftOp(code)) INT else resKind) - - val primitiveOp = code match { - case scalaPrimitives.ADD => Arithmetic(ADD, resKind) - case scalaPrimitives.SUB => Arithmetic(SUB, resKind) - case scalaPrimitives.MUL => Arithmetic(MUL, resKind) - case scalaPrimitives.DIV => Arithmetic(DIV, resKind) - case scalaPrimitives.MOD => Arithmetic(REM, resKind) - case scalaPrimitives.OR => Logical(OR, resKind) - case scalaPrimitives.XOR => Logical(XOR, resKind) - case scalaPrimitives.AND => Logical(AND, resKind) - case scalaPrimitives.LSL => Shift(LSL, resKind) - case scalaPrimitives.LSR => Shift(LSR, resKind) - case scalaPrimitives.ASR => Shift(ASR, resKind) - case _ => abort("Unknown primitive: " + fun.symbol + "[" + code + "]") - } - ctx1.bb.emit(CALL_PRIMITIVE(primitiveOp), tree.pos) - - case _ => - abort("Too many arguments for primitive function: " + tree) - } - (ctx1, resKind) - } - - /** Generate primitive array operations. - */ - private def genArrayOp(tree: Tree, ctx: Context, code: Int, expectedType: TypeKind): (Context, TypeKind) = { - import scalaPrimitives._ - val Apply(Select(arrayObj, _), args) = tree - val k = toTypeKind(arrayObj.tpe) - val ARRAY(elem) = k - var ctx1 = genLoad(arrayObj, ctx, k) - val elementType = typeOfArrayOp.getOrElse(code, abort("Unknown operation on arrays: " + tree + " code: " + code)) - - var generatedType = expectedType - - if (scalaPrimitives.isArrayGet(code)) { - // load argument on stack - debugassert(args.length == 1, - "Too many arguments for array get operation: " + tree) - ctx1 = genLoad(args.head, ctx1, INT) - generatedType = elem - ctx1.bb.emit(LOAD_ARRAY_ITEM(elementType), tree.pos) - // it's tempting to just drop array loads of type Null instead - // of adapting them but array accesses can cause - // ArrayIndexOutOfBounds so we can't. Besides, Array[Null] - // probably isn't common enough to figure out an optimization - adaptNullRef(generatedType, expectedType, ctx1, tree.pos) - } - else if (scalaPrimitives.isArraySet(code)) { - debugassert(args.length == 2, - "Too many arguments for array set operation: " + tree) - ctx1 = genLoad(args.head, ctx1, INT) - ctx1 = genLoad(args.tail.head, ctx1, toTypeKind(args.tail.head.tpe)) - // the following line should really be here, but because of bugs in erasure - // we pretend we generate whatever type is expected from us. - //generatedType = UNIT - - ctx1.bb.emit(STORE_ARRAY_ITEM(elementType), tree.pos) - } - else { - generatedType = INT - ctx1.bb.emit(CALL_PRIMITIVE(ArrayLength(elementType)), tree.pos) - } - - (ctx1, generatedType) - } - private def genSynchronized(tree: Apply, ctx: Context, expectedType: TypeKind): (Context, TypeKind) = { - val Apply(fun, args) = tree - val monitor = ctx.makeLocal(tree.pos, ObjectTpe, "monitor") - var monitorResult: Local = null - val argTpe = args.head.tpe - val hasResult = expectedType != UNIT - if (hasResult) - monitorResult = ctx.makeLocal(tree.pos, argTpe, "monitorResult") - - var ctx1 = genLoadQualifier(fun, ctx) - ctx1.bb.emit(Seq( - DUP(ObjectReference), - STORE_LOCAL(monitor), - MONITOR_ENTER() setPos tree.pos - )) - ctx1.enterSynchronized(monitor) - debuglog("synchronized block start") - - ctx1 = ctx1.Try( - bodyCtx => { - val ctx2 = genLoad(args.head, bodyCtx, expectedType /* toTypeKind(tree.tpe.resultType) */) - if (hasResult) - ctx2.bb.emit(STORE_LOCAL(monitorResult)) - ctx2.bb.emit(Seq( - LOAD_LOCAL(monitor), - MONITOR_EXIT() setPos tree.pos - )) - ctx2 - }, List( - // tree.tpe / fun.tpe is object, which is no longer true after this transformation - (ThrowableClass, expectedType, exhCtx => { - exhCtx.bb.emit(Seq( - LOAD_LOCAL(monitor), - MONITOR_EXIT() setPos tree.pos, - THROW(ThrowableClass) - )) - exhCtx.bb.enterIgnoreMode() - exhCtx - })), EmptyTree, tree) - - debuglog("synchronized block end with block %s closed=%s".format(ctx1.bb, ctx1.bb.closed)) - ctx1.exitSynchronized(monitor) - if (hasResult) - ctx1.bb.emit(LOAD_LOCAL(monitorResult)) - (ctx1, expectedType) - } - - private def genLoadIf(tree: If, ctx: Context, expectedType: TypeKind): (Context, TypeKind) = { - val If(cond, thenp, elsep) = tree - - var thenCtx = ctx.newBlock() - var elseCtx = ctx.newBlock() - val contCtx = ctx.newBlock() - - genCond(cond, ctx, thenCtx, elseCtx) - - val ifKind = toTypeKind(tree.tpe) - val thenKind = toTypeKind(thenp.tpe) - val elseKind = if (elsep == EmptyTree) UNIT else toTypeKind(elsep.tpe) - - // we need to drop unneeded results, if one branch gives - // unit and the other gives something on the stack, because - // the type of 'if' is scala.Any, and its erasure would be Object. - // But unboxed units are not Objects... - def hasUnitBranch = thenKind == UNIT || elseKind == UNIT - val resKind = if (hasUnitBranch) UNIT else ifKind - - if (hasUnitBranch) - debuglog("Will drop result from an if branch") - - thenCtx = genLoad(thenp, thenCtx, resKind) - elseCtx = genLoad(elsep, elseCtx, resKind) - - debugassert(!hasUnitBranch || expectedType == UNIT, - "I produce UNIT in a context where " + expectedType + " is expected!") - - // alternatives may be already closed by a tail-recursive jump - val contReachable = !(thenCtx.bb.ignore && elseCtx.bb.ignore) - thenCtx.bb.closeWith(JUMP(contCtx.bb)) - elseCtx.bb.closeWith( - if (elsep == EmptyTree) JUMP(contCtx.bb) - else JUMP(contCtx.bb) setPos tree.pos - ) - - contCtx.bb killUnless contReachable - (contCtx, resKind) - } - private def genLoadTry(tree: Try, ctx: Context, setGeneratedType: TypeKind => Unit): Context = { - val Try(block, catches, finalizer) = tree - val kind = toTypeKind(tree.tpe) - - val caseHandlers = - for (CaseDef(pat, _, body) <- catches.reverse) yield { - def genWildcardHandler(sym: Symbol): (Symbol, TypeKind, Context => Context) = - (sym, kind, ctx => { - ctx.bb.emit(DROP(REFERENCE(sym))) // drop the loaded exception - genLoad(body, ctx, kind) - }) - - pat match { - case Typed(Ident(nme.WILDCARD), tpt) => genWildcardHandler(tpt.tpe.typeSymbol) - case Ident(nme.WILDCARD) => genWildcardHandler(ThrowableClass) - case Bind(_, _) => - val exception = ctx.method addLocal new Local(pat.symbol, toTypeKind(pat.symbol.tpe), false) // the exception will be loaded and stored into this local - - (pat.symbol.tpe.typeSymbol, kind, { - ctx: Context => - ctx.bb.emit(STORE_LOCAL(exception), pat.pos) - genLoad(body, ctx, kind) - }) - } - } - - ctx.Try( - bodyCtx => { - setGeneratedType(kind) - genLoad(block, bodyCtx, kind) - }, - caseHandlers, - finalizer, - tree) - } - - private def genPrimitiveOp(tree: Apply, ctx: Context, expectedType: TypeKind): (Context, TypeKind) = { - val sym = tree.symbol - val Apply(fun @ Select(receiver, _), _) = tree - val code = scalaPrimitives.getPrimitive(sym, receiver.tpe) - - if (scalaPrimitives.isArithmeticOp(code)) - genArithmeticOp(tree, ctx, code) - else if (code == scalaPrimitives.CONCAT) - (genStringConcat(tree, ctx), StringReference) - else if (code == scalaPrimitives.HASH) - (genScalaHash(receiver, ctx), INT) - else if (isArrayOp(code)) - genArrayOp(tree, ctx, code, expectedType) - else if (isLogicalOp(code) || isComparisonOp(code)) { - val trueCtx, falseCtx, afterCtx = ctx.newBlock() - - genCond(tree, ctx, trueCtx, falseCtx) - trueCtx.bb.emitOnly( - CONSTANT(Constant(true)) setPos tree.pos, - JUMP(afterCtx.bb) - ) - falseCtx.bb.emitOnly( - CONSTANT(Constant(false)) setPos tree.pos, - JUMP(afterCtx.bb) - ) - (afterCtx, BOOL) - } - else if (code == scalaPrimitives.SYNCHRONIZED) - genSynchronized(tree, ctx, expectedType) - else if (scalaPrimitives.isCoercion(code)) { - val ctx1 = genLoad(receiver, ctx, toTypeKind(receiver.tpe)) - genCoercion(tree, ctx1, code) - (ctx1, scalaPrimitives.generatedKind(code)) - } - else abort( - "Primitive operation not handled yet: " + sym.fullName + "(" + - fun.symbol.simpleName + ") " + " at: " + (tree.pos) - ) - } - - /** - * Generate code for trees that produce values on the stack - * - * @param tree The tree to be translated - * @param ctx The current context - * @param expectedType The type of the value to be generated on top of the - * stack. - * @return The new context. The only thing that may change is the current - * basic block (as the labels map is mutable). - */ - private def genLoad(tree: Tree, ctx: Context, expectedType: TypeKind): Context = { - var generatedType = expectedType - debuglog("at line: " + (if (tree.pos.isDefined) tree.pos.line else tree.pos)) - - val resCtx: Context = tree match { - case LabelDef(name, params, rhs) => - def genLoadLabelDef = { - val ctx1 = ctx.newBlock() // note: we cannot kill ctx1 if ctx is in ignore mode because - // label defs can be the target of jumps from other locations. - // that means label defs can lead to unreachable code without - // proper reachability analysis - - if (nme.isLoopHeaderLabel(name)) - ctx1.bb.loopHeader = true - - ctx1.labels.get(tree.symbol) match { - case Some(label) => - debuglog("Found existing label for " + tree.symbol.fullLocationString) - label.anchor(ctx1.bb) - label.patch(ctx.method.code) - - case None => - val pair = (tree.symbol -> (new Label(tree.symbol) anchor ctx1.bb setParams (params map (_.symbol)))) - debuglog("Adding label " + tree.symbol.fullLocationString + " in genLoad.") - ctx1.labels += pair - ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false))) - } - - ctx.bb.closeWith(JUMP(ctx1.bb), tree.pos) - genLoad(rhs, ctx1, expectedType /*toTypeKind(tree.symbol.info.resultType)*/) - } - genLoadLabelDef - - case ValDef(_, name, _, rhs) => - def genLoadValDef = - if (name == nme.THIS) { - debuglog("skipping trivial assign to _$this: " + tree) - ctx - } else { - val sym = tree.symbol - val local = ctx.method.addLocal(new Local(sym, toTypeKind(sym.info), false)) - - if (rhs == EmptyTree) { - debuglog("Uninitialized variable " + tree + " at: " + (tree.pos)) - ctx.bb.emit(getZeroOf(local.kind)) - } - - var ctx1 = ctx - if (rhs != EmptyTree) - ctx1 = genLoad(rhs, ctx, local.kind) - - ctx1.bb.emit(STORE_LOCAL(local), tree.pos) - ctx1.scope.add(local) - ctx1.bb.emit(SCOPE_ENTER(local)) - generatedType = UNIT - ctx1 - } - genLoadValDef - - case t @ If(cond, thenp, elsep) => - val (newCtx, resKind) = genLoadIf(t, ctx, expectedType) - generatedType = resKind - newCtx - - case Return(expr) => - def genLoadReturn = { - val returnedKind = toTypeKind(expr.tpe) - debuglog("Return(" + expr + ") with returnedKind = " + returnedKind) - - var ctx1 = genLoad(expr, ctx, returnedKind) - lazy val tmp = ctx1.makeLocal(tree.pos, expr.tpe, "tmp") - val saved = savingCleanups(ctx1) { - var savedFinalizer = false - ctx1.cleanups foreach { - case MonitorRelease(m) => - debuglog("removing " + m + " from cleanups: " + ctx1.cleanups) - ctx1.bb.emit(Seq(LOAD_LOCAL(m), MONITOR_EXIT())) - ctx1.exitSynchronized(m) - - case Finalizer(f, finalizerCtx) => - debuglog("removing " + f + " from cleanups: " + ctx1.cleanups) - if (returnedKind != UNIT && mayCleanStack(f)) { - log("Emitting STORE_LOCAL for " + tmp + " to save finalizer.") - ctx1.bb.emit(STORE_LOCAL(tmp)) - savedFinalizer = true - } - - // duplicate finalizer (takes care of anchored labels) - val f1 = duplicateFinalizer(Set.empty ++ ctx1.labels.keySet, ctx1, f) - - // we have to run this without the same finalizer in - // the list, otherwise infinite recursion happens for - // finalizers that contain 'return' - val fctx = finalizerCtx.newBlock() - fctx.bb killIf ctx1.bb.ignore - ctx1.bb.closeWith(JUMP(fctx.bb)) - ctx1 = genLoad(f1, fctx, UNIT) - } - savedFinalizer - } - - if (saved) { - log("Emitting LOAD_LOCAL for " + tmp + " after saving finalizer.") - ctx1.bb.emit(LOAD_LOCAL(tmp)) - } - adapt(returnedKind, ctx1.method.returnType, ctx1, tree.pos) - ctx1.bb.emit(RETURN(ctx.method.returnType), tree.pos) - ctx1.bb.enterIgnoreMode() - generatedType = expectedType - ctx1 - } - genLoadReturn - - case t @ Try(_, _, _) => - genLoadTry(t, ctx, generatedType = _) - - case Throw(expr) => - val (ctx1, expectedType) = genThrow(expr, ctx) - generatedType = expectedType - ctx1 - - case New(tpt) => - abort("Unexpected New(" + tpt.summaryString + "/" + tpt + ") received in icode.\n" + - " Call was genLoad" + ((tree, ctx, expectedType))) - - case Apply(TypeApply(fun, targs), _) => - def genLoadApply1 = { - val sym = fun.symbol - val cast = sym match { - case Object_isInstanceOf => false - case Object_asInstanceOf => true - case _ => abort("Unexpected type application " + fun + "[sym: " + sym.fullName + "]" + " in: " + tree) - } - - val Select(obj, _) = fun - val l = toTypeKind(obj.tpe) - val r = toTypeKind(targs.head.tpe) - val ctx1 = genLoadQualifier(fun, ctx) - - if (l.isValueType && r.isValueType) - genConversion(l, r, ctx1, cast) - else if (l.isValueType) { - ctx1.bb.emit(DROP(l), fun.pos) - if (cast) { - ctx1.bb.emit(Seq( - NEW(REFERENCE(definitions.ClassCastExceptionClass)), - DUP(ObjectReference), - THROW(definitions.ClassCastExceptionClass) - )) - } else - ctx1.bb.emit(CONSTANT(Constant(false))) - } else if (r.isValueType && cast) { - /* Erasure should have added an unboxing operation to prevent that. */ - abort("should have been unboxed by erasure: " + tree) - } else if (r.isValueType) { - ctx.bb.emit(IS_INSTANCE(REFERENCE(definitions.boxedClass(r.toType.typeSymbol)))) - } else { - genCast(l, r, ctx1, cast) - } - generatedType = if (cast) r else BOOL - ctx1 - } - genLoadApply1 - - // 'super' call: Note: since constructors are supposed to - // return an instance of what they construct, we have to take - // special care. On JVM they are 'void', and Scala forbids (syntactically) - // to call super constructors explicitly and/or use their 'returned' value. - // therefore, we can ignore this fact, and generate code that leaves nothing - // on the stack (contrary to what the type in the AST says). - case Apply(fun @ Select(Super(_, mix), _), args) => - def genLoadApply2 = { - debuglog("Call to super: " + tree) - val invokeStyle = SuperCall(mix) - // if (fun.symbol.isConstructor) Static(true) else SuperCall(mix); - - ctx.bb.emit(THIS(ctx.clazz.symbol), tree.pos) - val ctx1 = genLoadArguments(args, fun.symbol.info.paramTypes, ctx) - - ctx1.bb.emit(CALL_METHOD(fun.symbol, invokeStyle), tree.pos) - generatedType = - if (fun.symbol.isConstructor) UNIT - else toTypeKind(fun.symbol.info.resultType) - ctx1 - } - genLoadApply2 - - // 'new' constructor call: Note: since constructors are - // thought to return an instance of what they construct, - // we have to 'simulate' it by DUPlicating the freshly created - // instance (on JVM, <init> methods return VOID). - case Apply(fun @ Select(New(tpt), nme.CONSTRUCTOR), args) => - def genLoadApply3 = { - val ctor = fun.symbol - debugassert(ctor.isClassConstructor, - "'new' call to non-constructor: " + ctor.name) - - generatedType = toTypeKind(tpt.tpe) - debugassert(generatedType.isReferenceType || generatedType.isArrayType, - "Non reference type cannot be instantiated: " + generatedType) - - generatedType match { - case arr @ ARRAY(elem) => - val ctx1 = genLoadArguments(args, ctor.info.paramTypes, ctx) - val dims = arr.dimensions - var elemKind = arr.elementKind - if (args.length > dims) - reporter.error(tree.pos, "too many arguments for array constructor: found " + args.length + - " but array has only " + dims + " dimension(s)") - if (args.length != dims) - for (i <- args.length until dims) elemKind = ARRAY(elemKind) - ctx1.bb.emit(CREATE_ARRAY(elemKind, args.length), tree.pos) - ctx1 - - case rt @ REFERENCE(cls) => - debugassert(ctor.owner == cls, - "Symbol " + ctor.owner.fullName + " is different than " + tpt) - - val nw = NEW(rt) - ctx.bb.emit(nw, tree.pos) - ctx.bb.emit(DUP(generatedType)) - val ctx1 = genLoadArguments(args, ctor.info.paramTypes, ctx) - - val init = CALL_METHOD(ctor, Static(onInstance = true)) - nw.init = init - ctx1.bb.emit(init, tree.pos) - ctx1 - case _ => - abort("Cannot instantiate " + tpt + " of kind: " + generatedType) - } - } - genLoadApply3 - - case Apply(fun @ _, List(expr)) if currentRun.runDefinitions.isBox(fun.symbol) => - def genLoadApply4 = { - debuglog("BOX : " + fun.symbol.fullName) - val ctx1 = genLoad(expr, ctx, toTypeKind(expr.tpe)) - val nativeKind = toTypeKind(expr.tpe) - if (settings.Xdce) { - // we store this boxed value to a local, even if not really needed. - // boxing optimization might use it, and dead code elimination will - // take care of unnecessary stores - val loc1 = ctx.makeLocal(tree.pos, expr.tpe, "boxed") - ctx1.bb.emit(STORE_LOCAL(loc1)) - ctx1.bb.emit(LOAD_LOCAL(loc1)) - } - ctx1.bb.emit(BOX(nativeKind), expr.pos) - generatedType = toTypeKind(fun.symbol.tpe.resultType) - ctx1 - } - genLoadApply4 - - case Apply(fun @ _, List(expr)) if (currentRun.runDefinitions.isUnbox(fun.symbol)) => - debuglog("UNBOX : " + fun.symbol.fullName) - val ctx1 = genLoad(expr, ctx, toTypeKind(expr.tpe)) - val boxType = toTypeKind(fun.symbol.owner.linkedClassOfClass.tpe) - generatedType = boxType - ctx1.bb.emit(UNBOX(boxType), expr.pos) - ctx1 - - case app @ Apply(fun, args) => - def genLoadApply6 = { - val sym = fun.symbol - - if (sym.isLabel) { // jump to a label - val label = ctx.labels.getOrElse(sym, { - // it is a forward jump, scan for labels - resolveForwardLabel(ctx.defdef, ctx, sym) - ctx.labels.get(sym) match { - case Some(l) => - debuglog("Forward jump for " + sym.fullLocationString + ": scan found label " + l) - l - case _ => - abort("Unknown label target: " + sym + " at: " + (fun.pos) + ": ctx: " + ctx) - } - }) - // note: when one of the args to genLoadLabelArguments is a jump to a label, - // it will call back into genLoad and arrive at this case, which will then set ctx1.bb.ignore to true, - // this is okay, since we're jumping unconditionally, so the loads and jumps emitted by the outer - // call to genLoad (by calling genLoadLabelArguments and emitOnly) can safely be ignored, - // however, as emitOnly will close the block, which reverses its instructions (when it's still open), - // we better not reverse when the block has already been closed but is in ignore mode - // (if it's not in ignore mode, double-closing is an error) - val ctx1 = genLoadLabelArguments(args, label, ctx) - ctx1.bb.emitOnly(if (label.anchored) JUMP(label.block) else PJUMP(label)) - ctx1.bb.enterIgnoreMode() - ctx1 - } else if (isPrimitive(sym)) { // primitive method call - val (newCtx, resKind) = genPrimitiveOp(app, ctx, expectedType) - generatedType = resKind - newCtx - } else { // normal method call - debuglog("Gen CALL_METHOD with sym: " + sym + " isStaticSymbol: " + sym.isStaticMember) - val invokeStyle = - if (sym.isStaticMember) - Static(onInstance = false) - else if (sym.isPrivate || sym.isClassConstructor) - Static(onInstance = true) - else - Dynamic - - var ctx1 = if (invokeStyle.hasInstance) genLoadQualifier(fun, ctx) else ctx - ctx1 = genLoadArguments(args, sym.info.paramTypes, ctx1) - val cm = CALL_METHOD(sym, invokeStyle) - - /* In a couple cases, squirrel away a little extra information in the - * CALL_METHOD for use by GenASM. - */ - fun match { - case Select(qual, _) => - val qualSym = findHostClass(qual.tpe, sym) - if (qualSym == ArrayClass) { - val kind = toTypeKind(qual.tpe) - cm setTargetTypeKind kind - log(s"Stored target type kind for {$sym.fullName} as $kind") - } - else { - cm setHostClass qualSym - if (qual.tpe.typeSymbol != qualSym) - log(s"Precisified host class for $sym from ${qual.tpe.typeSymbol.fullName} to ${qualSym.fullName}") - } - case _ => - } - ctx1.bb.emit(cm, tree.pos) - ctx1.method.updateRecursive(sym) - generatedType = - if (sym.isClassConstructor) UNIT - else toTypeKind(sym.info.resultType) - // deal with methods that return Null - adaptNullRef(generatedType, expectedType, ctx1, tree.pos) - ctx1 - } - } - genLoadApply6 - - case ApplyDynamic(qual, args) => - // TODO - this is where we'd catch dynamic applies for invokedynamic. - sys.error("No invokedynamic support yet.") - // val ctx1 = genLoad(qual, ctx, ObjectReference) - // genLoadArguments(args, tree.symbol.info.paramTypes, ctx1) - // ctx1.bb.emit(CALL_METHOD(tree.symbol, InvokeDynamic), tree.pos) - // ctx1 - - case This(qual) => - def genLoadThis = { - assert(tree.symbol == ctx.clazz.symbol || tree.symbol.isModuleClass, - "Trying to access the this of another class: " + - "tree.symbol = " + tree.symbol + ", ctx.clazz.symbol = " + ctx.clazz.symbol + " compilation unit:"+unit) - if (tree.symbol.isModuleClass && tree.symbol != ctx.clazz.symbol) { - genLoadModule(ctx, tree) - generatedType = REFERENCE(tree.symbol) - } else { - ctx.bb.emit(THIS(ctx.clazz.symbol), tree.pos) - generatedType = REFERENCE( - if (tree.symbol == ArrayClass) ObjectClass else ctx.clazz.symbol - ) - } - ctx - } - genLoadThis - - case Select(Ident(nme.EMPTY_PACKAGE_NAME), module) => - debugassert(tree.symbol.isModule, - "Selection of non-module from empty package: " + tree + - " sym: " + tree.symbol + " at: " + (tree.pos) - ) - genLoadModule(ctx, tree) - - case Select(qualifier, selector) => - def genLoadSelect = { - val sym = tree.symbol - generatedType = toTypeKind(sym.info) - val hostClass = findHostClass(qualifier.tpe, sym) - debuglog(s"Host class of $sym with qual $qualifier (${qualifier.tpe}) is $hostClass") - val qualSafeToElide = treeInfo isQualifierSafeToElide qualifier - - def genLoadQualUnlessElidable: Context = - if (qualSafeToElide) ctx else genLoadQualifier(tree, ctx) - - if (sym.isModule) { - genLoadModule(genLoadQualUnlessElidable, tree) - } else { - val isStatic = sym.isStaticMember - val ctx1 = if (isStatic) genLoadQualUnlessElidable - else genLoadQualifier(tree, ctx) - ctx1.bb.emit(LOAD_FIELD(sym, isStatic) setHostClass hostClass, tree.pos) - // it's tempting to drop field accesses of type Null instead of adapting them, - // but field access can cause static class init so we can't. Besides, fields - // of type Null probably aren't common enough to figure out an optimization - adaptNullRef(generatedType, expectedType, ctx1, tree.pos) - ctx1 - } - } - genLoadSelect - - case Ident(name) => - def genLoadIdent = { - val sym = tree.symbol - if (!sym.hasPackageFlag) { - if (sym.isModule) { - genLoadModule(ctx, tree) - generatedType = toTypeKind(sym.info) - } else { - ctx.method.lookupLocal(sym) match { - case Some(l) => - ctx.bb.emit(LOAD_LOCAL(l), tree.pos) - generatedType = l.kind - case None => - val saved = settings.uniqid - settings.uniqid.value = true - try { - val methodCode = unit.body.collect { case dd: DefDef - if dd.symbol == ctx.method.symbol => showCode(dd); - }.headOption.getOrElse("<unknown>") - abort(s"symbol $sym does not exist in ${ctx.method}, which contains locals ${ctx.method.locals.mkString(",")}. \nMethod code: $methodCode") - } - finally settings.uniqid.value = saved - } - } - } - ctx - } - genLoadIdent - - case Literal(value) => - def genLoadLiteral = { - if (value.tag != UnitTag) (value.tag, expectedType) match { - case (IntTag, LONG) => - ctx.bb.emit(CONSTANT(Constant(value.longValue)), tree.pos) - generatedType = LONG - case (FloatTag, DOUBLE) => - ctx.bb.emit(CONSTANT(Constant(value.doubleValue)), tree.pos) - generatedType = DOUBLE - case (NullTag, _) => - ctx.bb.emit(CONSTANT(value), tree.pos) - generatedType = NullReference - case _ => - ctx.bb.emit(CONSTANT(value), tree.pos) - generatedType = toTypeKind(tree.tpe) - } - ctx - } - genLoadLiteral - - case Block(stats, expr) => - ctx.enterScope() - var ctx1 = genStat(stats, ctx) - ctx1 = genLoad(expr, ctx1, expectedType) - ctx1.exitScope() - ctx1 - - case Typed(Super(_, _), _) => - genLoad(This(ctx.clazz.symbol), ctx, expectedType) - - case Typed(expr, _) => - genLoad(expr, ctx, expectedType) - - case Assign(_, _) => - generatedType = UNIT - genStat(tree, ctx) - - case ArrayValue(tpt @ TypeTree(), _elems) => - def genLoadArrayValue = { - var ctx1 = ctx - val elmKind = toTypeKind(tpt.tpe) - generatedType = ARRAY(elmKind) - val elems = _elems.toIndexedSeq - - ctx1.bb.emit(CONSTANT(new Constant(elems.length)), tree.pos) - ctx1.bb.emit(CREATE_ARRAY(elmKind, 1)) - // inline array literals - var i = 0 - while (i < elems.length) { - ctx1.bb.emit(DUP(generatedType), tree.pos) - ctx1.bb.emit(CONSTANT(new Constant(i))) - ctx1 = genLoad(elems(i), ctx1, elmKind) - ctx1.bb.emit(STORE_ARRAY_ITEM(elmKind)) - i = i + 1 - } - ctx1 - } - genLoadArrayValue - - case Match(selector, cases) => - def genLoadMatch = { - debuglog("Generating SWITCH statement.") - val ctx1 = genLoad(selector, ctx, INT) // TODO: Java 7 allows strings in switches (so, don't assume INT and don't convert the literals using intValue) - val afterCtx = ctx1.newBlock() - afterCtx.bb killIf ctx1.bb.ignore - var afterCtxReachable = false - var caseCtx: Context = null - generatedType = toTypeKind(tree.tpe) - - var targets: List[BasicBlock] = Nil - var tags: List[Int] = Nil - var default: BasicBlock = afterCtx.bb - - for (caze @ CaseDef(pat, guard, body) <- cases) { - assert(guard == EmptyTree, guard) - val tmpCtx = ctx1.newBlock() - tmpCtx.bb killIf ctx1.bb.ignore - pat match { - case Literal(value) => - tags = value.intValue :: tags - targets = tmpCtx.bb :: targets - case Ident(nme.WILDCARD) => - default = tmpCtx.bb - case Alternative(alts) => - alts foreach { - case Literal(value) => - tags = value.intValue :: tags - targets = tmpCtx.bb :: targets - case _ => - abort("Invalid case in alternative in switch-like pattern match: " + - tree + " at: " + tree.pos) - } - case _ => - abort("Invalid case statement in switch-like pattern match: " + - tree + " at: " + (tree.pos)) - } - - caseCtx = genLoad(body, tmpCtx, generatedType) - afterCtxReachable ||= !caseCtx.bb.ignore - // close the block unless it's already been closed by the body, which closes the block if it ends in a jump (which is emitted to have alternatives share their body) - caseCtx.bb.closeWith(JUMP(afterCtx.bb) setPos caze.pos) - } - afterCtxReachable ||= (default == afterCtx) - ctx1.bb.emitOnly( - SWITCH(tags.reverse map (x => List(x)), (default :: targets).reverse) setPos tree.pos - ) - afterCtx.bb killUnless afterCtxReachable - afterCtx - } - genLoadMatch - - case EmptyTree => - if (expectedType != UNIT) - ctx.bb.emit(getZeroOf(expectedType)) - ctx - - case _ => - abort("Unexpected tree in genLoad: " + tree + "/" + tree.getClass + " at: " + tree.pos) - } - - // emit conversion - if (generatedType != expectedType) { - tree match { - case Literal(Constant(null)) if generatedType == NullReference && expectedType != UNIT => - // literal null on the stack (as opposed to a boxed null, see SI-8233), - // we can bypass `adapt` which would otherwise emit a redundant [DROP, CONSTANT(null)] - // except one case: when expected type is UNIT (unboxed) where we need to emit just a DROP - case _ => - adapt(generatedType, expectedType, resCtx, tree.pos) - } - } - - resCtx - } - - /** - * If we have a method call, field load, or array element load of type Null then - * we need to convince the JVM that we have a null value because in Scala - * land Null is a subtype of all ref types, but in JVM land scala.runtime.Null$ - * is not. Note we don't have to adapt loads of locals because the JVM type - * system for locals does have a null type which it tracks internally. As - * long as we adapt these other things, the JVM will know that a Scala local of - * type Null is holding a null. - */ - private def adaptNullRef(from: TypeKind, to: TypeKind, ctx: Context, pos: Position) { - debuglog(s"GenICode#adaptNullRef($from, $to, $ctx, $pos)") - - // Don't need to adapt null to unit because we'll just drop it anyway. Don't - // need to adapt to Object or AnyRef because the JVM is happy with - // upcasting Null to them. - // We do have to adapt from NullReference to NullReference because we could be storing - // this value into a local of type Null and we want the JVM to see that it's - // a null value so we don't have to also adapt local loads. - if (from == NullReference && to != UNIT && to != ObjectReference && to != AnyRefReference) { - assert(to.isRefOrArrayType, s"Attempt to adapt a null to a non reference type $to.") - // adapt by dropping what we've got and pushing a null which - // will convince the JVM we really do have null - ctx.bb.emit(DROP(from), pos) - ctx.bb.emit(CONSTANT(Constant(null)), pos) - } - } - - private def adapt(from: TypeKind, to: TypeKind, ctx: Context, pos: Position) { - // An awful lot of bugs explode here - let's leave ourselves more clues. - // A typical example is an overloaded type assigned after typer. - debuglog(s"GenICode#adapt($from, $to, $ctx, $pos)") - - def coerce(from: TypeKind, to: TypeKind) = ctx.bb.emit(CALL_PRIMITIVE(Conversion(from, to)), pos) - - (from, to) match { - // The JVM doesn't have a Nothing equivalent, so it doesn't know that a method of type Nothing can't actually return. So for instance, with - // def f: String = ??? - // we need - // 0: getstatic #25; //Field scala/Predef$.MODULE$:Lscala/Predef$; - // 3: invokevirtual #29; //Method scala/Predef$.$qmark$qmark$qmark:()Lscala/runtime/Nothing$; - // 6: athrow - // So this case tacks on the ahtrow which makes the JVM happy because class Nothing is declared as a subclass of Throwable - case (NothingReference, _) => - ctx.bb.emit(THROW(ThrowableClass)) - ctx.bb.enterIgnoreMode() - case (NullReference, REFERENCE(_)) => - // SI-8223 we can't assume that the stack contains a `null`, it might contain a Null$ - ctx.bb.emit(Seq(DROP(from), CONSTANT(Constant(null)))) - case _ if from isAssignabledTo to => - () - case (_, UNIT) => - ctx.bb.emit(DROP(from), pos) - // otherwise we'd better be doing a primitive -> primitive coercion or there's a problem - case _ if !from.isRefOrArrayType && !to.isRefOrArrayType => - coerce(from, to) - case _ => - assert(false, s"Can't convert from $from to $to in unit ${unit.source} at $pos") - } - } - - /** Load the qualifier of `tree` on top of the stack. */ - private def genLoadQualifier(tree: Tree, ctx: Context): Context = - tree match { - case Select(qualifier, _) => - genLoad(qualifier, ctx, toTypeKind(qualifier.tpe)) - case _ => - abort("Unknown qualifier " + tree) - } - - /** - * Generate code that loads args into label parameters. - */ - private def genLoadLabelArguments(args: List[Tree], label: Label, ctx: Context): Context = { - debugassert( - args.length == label.params.length, - "Wrong number of arguments in call to label " + label.symbol - ) - var ctx1 = ctx - - def isTrivial(kv: (Tree, Symbol)) = kv match { - case (This(_), p) if p.name == nme.THIS => true - case (arg @ Ident(_), p) if arg.symbol == p => true - case _ => false - } - - val stores = args zip label.params filterNot isTrivial map { - case (arg, param) => - val local = ctx.method.lookupLocal(param).get - ctx1 = genLoad(arg, ctx1, local.kind) - - val store = - if (param.name == nme.THIS) STORE_THIS(toTypeKind(ctx1.clazz.symbol.tpe)) - else STORE_LOCAL(local) - - store setPos arg.pos - } - - // store arguments in reverse order on the stack - ctx1.bb.emit(stores.reverse) - ctx1 - } - - private def genLoadArguments(args: List[Tree], tpes: List[Type], ctx: Context): Context = - (args zip tpes).foldLeft(ctx) { - case (res, (arg, tpe)) => - genLoad(arg, res, toTypeKind(tpe)) - } - - private def genLoadModule(ctx: Context, tree: Tree): Context = { - // Working around SI-5604. Rather than failing the compile when we see - // a package here, check if there's a package object. - val sym = ( - if (!tree.symbol.isPackageClass) tree.symbol - else tree.symbol.info.member(nme.PACKAGE) match { - case NoSymbol => abort("Cannot use package as value: " + tree) - case s => - devWarning(s"Found ${tree.symbol} where a package object is required. Converting to ${s.moduleClass}") - s.moduleClass - } - ) - debuglog("LOAD_MODULE from %s: %s".format(tree.shortClass, sym)) - ctx.bb.emit(LOAD_MODULE(sym), tree.pos) - ctx - } - - def genConversion(from: TypeKind, to: TypeKind, ctx: Context, cast: Boolean) = { - if (cast) - ctx.bb.emit(CALL_PRIMITIVE(Conversion(from, to))) - else { - ctx.bb.emit(DROP(from)) - ctx.bb.emit(CONSTANT(Constant(from == to))) - } - } - - def genCast(from: TypeKind, to: TypeKind, ctx: Context, cast: Boolean) = - ctx.bb.emit(if (cast) CHECK_CAST(to) else IS_INSTANCE(to)) - - def getZeroOf(k: TypeKind): Instruction = k match { - case UNIT => CONSTANT(Constant(())) - case BOOL => CONSTANT(Constant(false)) - case BYTE => CONSTANT(Constant(0: Byte)) - case SHORT => CONSTANT(Constant(0: Short)) - case CHAR => CONSTANT(Constant(0: Char)) - case INT => CONSTANT(Constant(0: Int)) - case LONG => CONSTANT(Constant(0: Long)) - case FLOAT => CONSTANT(Constant(0.0f)) - case DOUBLE => CONSTANT(Constant(0.0d)) - case REFERENCE(cls) => CONSTANT(Constant(null: Any)) - case ARRAY(elem) => CONSTANT(Constant(null: Any)) - case BOXED(_) => CONSTANT(Constant(null: Any)) - case ConcatClass => abort("no zero of ConcatClass") - } - - - /** Is the given symbol a primitive operation? */ - def isPrimitive(fun: Symbol): Boolean = scalaPrimitives.isPrimitive(fun) - - /** Generate coercion denoted by "code" - */ - def genCoercion(tree: Tree, ctx: Context, code: Int) = { - import scalaPrimitives._ - (code: @switch) match { - case B2B => () - case B2C => ctx.bb.emit(CALL_PRIMITIVE(Conversion(BYTE, CHAR)), tree.pos) - case B2S => ctx.bb.emit(CALL_PRIMITIVE(Conversion(BYTE, SHORT)), tree.pos) - case B2I => ctx.bb.emit(CALL_PRIMITIVE(Conversion(BYTE, INT)), tree.pos) - case B2L => ctx.bb.emit(CALL_PRIMITIVE(Conversion(BYTE, LONG)), tree.pos) - case B2F => ctx.bb.emit(CALL_PRIMITIVE(Conversion(BYTE, FLOAT)), tree.pos) - case B2D => ctx.bb.emit(CALL_PRIMITIVE(Conversion(BYTE, DOUBLE)), tree.pos) - - case S2B => ctx.bb.emit(CALL_PRIMITIVE(Conversion(SHORT, BYTE)), tree.pos) - case S2S => () - case S2C => ctx.bb.emit(CALL_PRIMITIVE(Conversion(SHORT, CHAR)), tree.pos) - case S2I => ctx.bb.emit(CALL_PRIMITIVE(Conversion(SHORT, INT)), tree.pos) - case S2L => ctx.bb.emit(CALL_PRIMITIVE(Conversion(SHORT, LONG)), tree.pos) - case S2F => ctx.bb.emit(CALL_PRIMITIVE(Conversion(SHORT, FLOAT)), tree.pos) - case S2D => ctx.bb.emit(CALL_PRIMITIVE(Conversion(SHORT, DOUBLE)), tree.pos) - - case C2B => ctx.bb.emit(CALL_PRIMITIVE(Conversion(CHAR, BYTE)), tree.pos) - case C2S => ctx.bb.emit(CALL_PRIMITIVE(Conversion(CHAR, SHORT)), tree.pos) - case C2C => () - case C2I => ctx.bb.emit(CALL_PRIMITIVE(Conversion(CHAR, INT)), tree.pos) - case C2L => ctx.bb.emit(CALL_PRIMITIVE(Conversion(CHAR, LONG)), tree.pos) - case C2F => ctx.bb.emit(CALL_PRIMITIVE(Conversion(CHAR, FLOAT)), tree.pos) - case C2D => ctx.bb.emit(CALL_PRIMITIVE(Conversion(CHAR, DOUBLE)), tree.pos) - - case I2B => ctx.bb.emit(CALL_PRIMITIVE(Conversion(INT, BYTE)), tree.pos) - case I2S => ctx.bb.emit(CALL_PRIMITIVE(Conversion(INT, SHORT)), tree.pos) - case I2C => ctx.bb.emit(CALL_PRIMITIVE(Conversion(INT, CHAR)), tree.pos) - case I2I => () - case I2L => ctx.bb.emit(CALL_PRIMITIVE(Conversion(INT, LONG)), tree.pos) - case I2F => ctx.bb.emit(CALL_PRIMITIVE(Conversion(INT, FLOAT)), tree.pos) - case I2D => ctx.bb.emit(CALL_PRIMITIVE(Conversion(INT, DOUBLE)), tree.pos) - - case L2B => ctx.bb.emit(CALL_PRIMITIVE(Conversion(LONG, BYTE)), tree.pos) - case L2S => ctx.bb.emit(CALL_PRIMITIVE(Conversion(LONG, SHORT)), tree.pos) - case L2C => ctx.bb.emit(CALL_PRIMITIVE(Conversion(LONG, CHAR)), tree.pos) - case L2I => ctx.bb.emit(CALL_PRIMITIVE(Conversion(LONG, INT)), tree.pos) - case L2L => () - case L2F => ctx.bb.emit(CALL_PRIMITIVE(Conversion(LONG, FLOAT)), tree.pos) - case L2D => ctx.bb.emit(CALL_PRIMITIVE(Conversion(LONG, DOUBLE)), tree.pos) - - case F2B => ctx.bb.emit(CALL_PRIMITIVE(Conversion(FLOAT, BYTE)), tree.pos) - case F2S => ctx.bb.emit(CALL_PRIMITIVE(Conversion(FLOAT, SHORT)), tree.pos) - case F2C => ctx.bb.emit(CALL_PRIMITIVE(Conversion(FLOAT, CHAR)), tree.pos) - case F2I => ctx.bb.emit(CALL_PRIMITIVE(Conversion(FLOAT, INT)), tree.pos) - case F2L => ctx.bb.emit(CALL_PRIMITIVE(Conversion(FLOAT, LONG)), tree.pos) - case F2F => () - case F2D => ctx.bb.emit(CALL_PRIMITIVE(Conversion(FLOAT, DOUBLE)), tree.pos) - - case D2B => ctx.bb.emit(CALL_PRIMITIVE(Conversion(DOUBLE, BYTE)), tree.pos) - case D2S => ctx.bb.emit(CALL_PRIMITIVE(Conversion(DOUBLE, SHORT)), tree.pos) - case D2C => ctx.bb.emit(CALL_PRIMITIVE(Conversion(DOUBLE, CHAR)), tree.pos) - case D2I => ctx.bb.emit(CALL_PRIMITIVE(Conversion(DOUBLE, INT)), tree.pos) - case D2L => ctx.bb.emit(CALL_PRIMITIVE(Conversion(DOUBLE, LONG)), tree.pos) - case D2F => ctx.bb.emit(CALL_PRIMITIVE(Conversion(DOUBLE, FLOAT)), tree.pos) - case D2D => () - - case _ => abort("Unknown coercion primitive: " + code) - } - } - - /** The Object => String overload. - */ - private lazy val String_valueOf: Symbol = getMember(StringModule, nme.valueOf) filter (sym => - sym.info.paramTypes match { - case List(pt) => pt.typeSymbol == ObjectClass - case _ => false - } - ) - - // I wrote it this way before I realized all the primitive types are - // boxed at this point, so I'd have to unbox them. Keeping it around in - // case we want to get more precise. - // - // private def valueOfForType(tp: Type): Symbol = { - // val xs = getMember(StringModule, nme.valueOf) filter (sym => - // // We always exclude the Array[Char] overload because java throws an NPE if - // // you pass it a null. It will instead find the Object one, which doesn't. - // sym.info.paramTypes match { - // case List(pt) => pt.typeSymbol != ArrayClass && (tp <:< pt) - // case _ => false - // } - // ) - // xs.alternatives match { - // case List(sym) => sym - // case _ => NoSymbol - // } - // } - - /** Generate string concatenation. - */ - def genStringConcat(tree: Tree, ctx: Context): Context = { - liftStringConcat(tree) match { - // Optimization for expressions of the form "" + x. We can avoid the StringBuilder. - case List(Literal(Constant("")), arg) => - debuglog("Rewriting \"\" + x as String.valueOf(x) for: " + arg) - val ctx1 = genLoad(arg, ctx, ObjectReference) - ctx1.bb.emit(CALL_METHOD(String_valueOf, Static(onInstance = false)), arg.pos) - ctx1 - case concatenations => - debuglog("Lifted string concatenations for " + tree + "\n to: " + concatenations) - var ctx1 = ctx - ctx1.bb.emit(CALL_PRIMITIVE(StartConcat), tree.pos) - for (elem <- concatenations) { - val kind = toTypeKind(elem.tpe) - ctx1 = genLoad(elem, ctx1, kind) - ctx1.bb.emit(CALL_PRIMITIVE(StringConcat(kind)), elem.pos) - } - ctx1.bb.emit(CALL_PRIMITIVE(EndConcat), tree.pos) - ctx1 - } - } - - /** Generate the scala ## method. - */ - def genScalaHash(tree: Tree, ctx: Context): Context = { - val hashMethod = { - ctx.bb.emit(LOAD_MODULE(ScalaRunTimeModule)) - getMember(ScalaRunTimeModule, nme.hash_) - } - - val ctx1 = genLoad(tree, ctx, ObjectReference) - ctx1.bb.emit(CALL_METHOD(hashMethod, Static(onInstance = false))) - ctx1 - } - - /** - * Returns a list of trees that each should be concatenated, from - * left to right. It turns a chained call like "a".+("b").+("c") into - * a list of arguments. - */ - def liftStringConcat(tree: Tree): List[Tree] = tree match { - case Apply(fun @ Select(larg, method), rarg) => - if (isPrimitive(fun.symbol) && - scalaPrimitives.getPrimitive(fun.symbol) == scalaPrimitives.CONCAT) - liftStringConcat(larg) ::: rarg - else - List(tree) - case _ => - List(tree) - } - - /** - * Find the label denoted by `lsym` and enter it in context `ctx`. - * - * We only enter one symbol at a time, even though we might traverse the same - * tree more than once per method. That's because we cannot enter labels that - * might be duplicated (for instance, inside finally blocks). - * - * TODO: restrict the scanning to smaller subtrees than the whole method. - * It is sufficient to scan the trees of the innermost enclosing block. - */ - private def resolveForwardLabel(tree: Tree, ctx: Context, lsym: Symbol): Unit = tree foreachPartial { - case t @ LabelDef(_, params, rhs) if t.symbol == lsym => - ctx.labels.getOrElseUpdate(t.symbol, { - val locals = params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false)) - ctx.method addLocals locals - - new Label(t.symbol) setParams (params map (_.symbol)) - }) - rhs - } - - /** - * Generate code for conditional expressions. The two basic blocks - * represent the continuation in case of success/failure of the - * test. - */ - private def genCond(tree: Tree, - ctx: Context, - thenCtx: Context, - elseCtx: Context): Boolean = - { - /** - * Generate the de-sugared comparison mechanism that will underly an '==' - * - * @param l left-hand side of the '==' - * @param r right-hand side of the '==' - * @param code the comparison operator to use - * @return true if either branch can continue normally to a follow on block, false otherwise - */ - def genComparisonOp(l: Tree, r: Tree, code: Int): Boolean = { - val op: TestOp = code match { - case scalaPrimitives.LT => LT - case scalaPrimitives.LE => LE - case scalaPrimitives.GT => GT - case scalaPrimitives.GE => GE - case scalaPrimitives.ID | scalaPrimitives.EQ => EQ - case scalaPrimitives.NI | scalaPrimitives.NE => NE - - case _ => abort("Unknown comparison primitive: " + code) - } - - // special-case reference (in)equality test for null (null eq x, x eq null) - lazy val nonNullSide = ifOneIsNull(l, r) - if (isReferenceEqualityOp(code) && nonNullSide != null) { - val ctx1 = genLoad(nonNullSide, ctx, ObjectReference) - val branchesReachable = !ctx1.bb.ignore - ctx1.bb.emitOnly( - CZJUMP(thenCtx.bb, elseCtx.bb, op, ObjectReference) - ) - branchesReachable - } - else { - val kind = getMaxType(l.tpe :: r.tpe :: Nil) - var ctx1 = genLoad(l, ctx, kind) - ctx1 = genLoad(r, ctx1, kind) - val branchesReachable = !ctx1.bb.ignore - - ctx1.bb.emitOnly( - CJUMP(thenCtx.bb, elseCtx.bb, op, kind) setPos r.pos - ) - branchesReachable - } - } - - debuglog("Entering genCond with tree: " + tree) - - // the default emission - def default(): Boolean = { - val ctx1 = genLoad(tree, ctx, BOOL) - val branchesReachable = !ctx1.bb.ignore - ctx1.bb.closeWith(CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) setPos tree.pos) - branchesReachable - } - - tree match { - // The comparison symbol is in ScalaPrimitives's "primitives" map - case Apply(fun, args) if isPrimitive(fun.symbol) => - import scalaPrimitives.{ ZNOT, ZAND, ZOR, EQ, getPrimitive } - - // lhs and rhs of test - lazy val Select(lhs, _) = fun - lazy val rhs = args.head - - def genZandOrZor(and: Boolean): Boolean = { - val ctxInterm = ctx.newBlock() - - val lhsBranchesReachable = if (and) genCond(lhs, ctx, ctxInterm, elseCtx) - else genCond(lhs, ctx, thenCtx, ctxInterm) - // If lhs is known to throw, we can kill the just created ctxInterm. - ctxInterm.bb killUnless lhsBranchesReachable - - val rhsBranchesReachable = genCond(rhs, ctxInterm, thenCtx, elseCtx) - - // Reachable means "it does not always throw", i.e. "it might not throw". - // In an expression (a && b) or (a || b), the b branch might not be evaluated. - // Such an expression is therefore known to throw only if both expressions throw. Or, - // successors are reachable if either of the two is reachable (SI-8625). - lhsBranchesReachable || rhsBranchesReachable - } - def genRefEq(isEq: Boolean) = { - val f = genEqEqPrimitive(lhs, rhs, ctx) _ - if (isEq) f(thenCtx, elseCtx) - else f(elseCtx, thenCtx) - } - - getPrimitive(fun.symbol) match { - case ZNOT => genCond(lhs, ctx, elseCtx, thenCtx) - case ZAND => genZandOrZor(and = true) - case ZOR => genZandOrZor(and = false) - case code => - // x == y where LHS is reference type - if (isUniversalEqualityOp(code) && toTypeKind(lhs.tpe).isReferenceType) { - if (code == EQ) genRefEq(isEq = true) - else genRefEq(isEq = false) - } - else if (isComparisonOp(code)) - genComparisonOp(lhs, rhs, code) - else - default() - } - - case _ => default() - } - } - - /** - * Generate the "==" code for object references. It is equivalent of - * if (l eq null) r eq null else l.equals(r); - * - * @param l left-hand side of the '==' - * @param r right-hand side of the '==' - * @param ctx current context - * @param thenCtx target context if the comparison yields true - * @param elseCtx target context if the comparison yields false - * @return true if either branch can continue normally to a follow on block, false otherwise - */ - def genEqEqPrimitive(l: Tree, r: Tree, ctx: Context)(thenCtx: Context, elseCtx: Context): Boolean = { - def getTempLocal = ctx.method.lookupLocal(nme.EQEQ_LOCAL_VAR) getOrElse { - ctx.makeLocal(l.pos, AnyRefTpe, nme.EQEQ_LOCAL_VAR.toString) - } - - /* True if the equality comparison is between values that require the use of the rich equality - * comparator (scala.runtime.Comparator.equals). This is the case when either side of the - * comparison might have a run-time type subtype of java.lang.Number or java.lang.Character. - * When it is statically known that both sides are equal and subtypes of Number of Character, - * not using the rich equality is possible (their own equals method will do ok.)*/ - def mustUseAnyComparator: Boolean = { - def areSameFinals = l.tpe.isFinalType && r.tpe.isFinalType && (l.tpe =:= r.tpe) - !areSameFinals && isMaybeBoxed(l.tpe.typeSymbol) && isMaybeBoxed(r.tpe.typeSymbol) - } - - if (mustUseAnyComparator) { - // when -optimise is on we call the @inline-version of equals, found in ScalaRunTime - val equalsMethod: Symbol = { - if (!settings.optimise) { - if (l.tpe <:< BoxedNumberClass.tpe) { - if (r.tpe <:< BoxedNumberClass.tpe) platform.externalEqualsNumNum - else if (r.tpe <:< BoxedCharacterClass.tpe) platform.externalEqualsNumObject // will be externalEqualsNumChar in 2.12, SI-9030 - else platform.externalEqualsNumObject - } else platform.externalEquals - } else { - ctx.bb.emit(LOAD_MODULE(ScalaRunTimeModule)) - getMember(ScalaRunTimeModule, nme.inlinedEquals) - } - } - - val ctx1 = genLoad(l, ctx, ObjectReference) - val ctx2 = genLoad(r, ctx1, ObjectReference) - val branchesReachable = !ctx2.bb.ignore - ctx2.bb.emitOnly( - CALL_METHOD(equalsMethod, if (settings.optimise) Dynamic else Static(onInstance = false)), - CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) - ) - branchesReachable - } - else { - if (isNull(l)) { - // null == expr -> expr eq null - val ctx1 = genLoad(r, ctx, ObjectReference) - val branchesReachable = !ctx1.bb.ignore - ctx1.bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) - branchesReachable - } else if (isNull(r)) { - // expr == null -> expr eq null - val ctx1 = genLoad(l, ctx, ObjectReference) - val branchesReachable = !ctx1.bb.ignore - ctx1.bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) - branchesReachable - } else if (isNonNullExpr(l)) { - // Avoid null check if L is statically non-null. - // - // "" == expr -> "".equals(expr) - // Nil == expr -> Nil.equals(expr) - // - // Common enough (through pattern matching) to treat this specially here rather than - // hoping that -Yconst-opt is enabled. The impossible branches for null checks lead - // to spurious "branch not covered" warnings in Jacoco code coverage. - var ctx1 = genLoad(l, ctx, ObjectReference) - val branchesReachable = !ctx1.bb.ignore - ctx1 = genLoad(r, ctx1, ObjectReference) - ctx1.bb emitOnly( - CALL_METHOD(Object_equals, Dynamic), - CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) - ) - branchesReachable - } else { - val eqEqTempLocal = getTempLocal - var ctx1 = genLoad(l, ctx, ObjectReference) - val branchesReachable = !ctx1.bb.ignore - lazy val nonNullCtx = { - val block = ctx1.newBlock() - block.bb killUnless branchesReachable - block - } - - // l == r -> if (l eq null) r eq null else l.equals(r) - ctx1 = genLoad(r, ctx1, ObjectReference) - val nullCtx = ctx1.newBlock() - nullCtx.bb killUnless branchesReachable - - ctx1.bb.emitOnly( - STORE_LOCAL(eqEqTempLocal) setPos l.pos, - DUP(ObjectReference), - CZJUMP(nullCtx.bb, nonNullCtx.bb, EQ, ObjectReference) - ) - nullCtx.bb.emitOnly( - DROP(ObjectReference) setPos l.pos, // type of AnyRef - LOAD_LOCAL(eqEqTempLocal), - CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) - ) - nonNullCtx.bb.emitOnly( - LOAD_LOCAL(eqEqTempLocal) setPos l.pos, - CALL_METHOD(Object_equals, Dynamic), - CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) - ) - branchesReachable - } - } - } - - /** - * Add all fields of the given class symbol to the current ICode - * class. - */ - private def addClassFields(ctx: Context, cls: Symbol) { - debugassert(ctx.clazz.symbol eq cls, - "Classes are not the same: " + ctx.clazz.symbol + ", " + cls) - - /* Non-method term members are fields, except for module members. Module - * members can only happen on .NET (no flatten) for inner traits. There, - * a module symbol is generated (transformInfo in mixin) which is used - * as owner for the members of the implementation class (so that the - * backend emits them as static). - * No code is needed for this module symbol. - */ - for (f <- cls.info.decls ; if !f.isMethod && f.isTerm && !f.isModule) - ctx.clazz addField new IField(f) - } - - /** - * Add parameters to the current ICode method. It is assumed the methods - * have been uncurried, so the list of lists contains just one list. - */ - private def addMethodParams(ctx: Context, vparamss: List[List[ValDef]]) { - vparamss match { - case Nil => () - - case vparams :: Nil => - for (p <- vparams) { - val lv = new Local(p.symbol, toTypeKind(p.symbol.info), true) - ctx.method.addParam(lv) - ctx.scope.add(lv) - ctx.bb.varsInScope += lv - } - ctx.method.params = ctx.method.params.reverse - - case _ => - abort("Malformed parameter list: " + vparamss) - } - } - - /** Does this tree have a try-catch block? */ - def mayCleanStack(tree: Tree): Boolean = tree exists { - case Try(_, _, _) => true - case _ => false - } - - /** - * If the block consists of a single unconditional jump, prune - * it by replacing the instructions in the predecessor to jump - * directly to the JUMP target of the block. - */ - def prune(method: IMethod) = { - var changed = false - var n = 0 - - def prune0(block: BasicBlock): Unit = { - val optCont = block.lastInstruction match { - case JUMP(b) if (b != block) => Some(b) - case _ => None - } - if (block.size == 1 && optCont.isDefined) { - val Some(cont) = optCont - val pred = block.predecessors - debuglog("Preds: " + pred + " of " + block + " (" + optCont + ")") - pred foreach { p => - changed = true - p.lastInstruction match { - case CJUMP(succ, fail, cond, kind) if (succ == block || fail == block) => - debuglog("Pruning empty if branch.") - p.replaceInstruction(p.lastInstruction, - if (block == succ) - if (block == fail) - CJUMP(cont, cont, cond, kind) - else - CJUMP(cont, fail, cond, kind) - else if (block == fail) - CJUMP(succ, cont, cond, kind) - else - abort("Could not find block in preds: " + method + " " + block + " " + pred + " " + p)) - - case CZJUMP(succ, fail, cond, kind) if (succ == block || fail == block) => - debuglog("Pruning empty ifz branch.") - p.replaceInstruction(p.lastInstruction, - if (block == succ) - if (block == fail) - CZJUMP(cont, cont, cond, kind) - else - CZJUMP(cont, fail, cond, kind) - else if (block == fail) - CZJUMP(succ, cont, cond, kind) - else - abort("Could not find block in preds")) - - case JUMP(b) if (b == block) => - debuglog("Pruning empty JMP branch.") - val replaced = p.replaceInstruction(p.lastInstruction, JUMP(cont)) - debugassert(replaced, "Didn't find p.lastInstruction") - - case SWITCH(tags, labels) if (labels contains block) => - debuglog("Pruning empty SWITCH branch.") - p.replaceInstruction(p.lastInstruction, - SWITCH(tags, labels map (l => if (l == block) cont else l))) - - // the last instr of the predecessor `p` is not a jump to the block `block`. - // this happens when `block` is part of an exception handler covering `b`. - case _ => () - } - } - if (changed) { - debuglog("Removing block: " + block) - method.code.removeBlock(block) - for (e <- method.exh) { - e.covered = e.covered filter (_ != block) - e.blocks = e.blocks filter (_ != block) - if (e.startBlock eq block) - e setStartBlock cont - } - } - } - } - - do { - changed = false - n += 1 - method.blocks foreach prune0 - } while (changed) - - debuglog("Prune fixpoint reached in " + n + " iterations.") - } - - def getMaxType(ts: List[Type]): TypeKind = - ts map toTypeKind reduceLeft (_ maxType _) - - /** Tree transformer that duplicates code and at the same time creates - * fresh symbols for existing labels. Since labels may be used before - * they are defined (forward jumps), all labels found are mapped to fresh - * symbols. References to the same label (use or definition) will remain - * consistent after this transformation (both the use and the definition of - * some label l will be mapped to the same label l'). - * - * Note: If the tree fragment passed to the duplicator contains unbound - * label names, the bind to the outer labeldef will be lost! That's because - * a use of an unbound label l will be transformed to l', and the corresponding - * label def, being outside the scope of this transformation, will not be updated. - * - * All LabelDefs are entered into the context label map, since it makes no sense - * to delay it any more: they will be used at some point. - */ - class DuplicateLabels(boundLabels: Set[Symbol]) extends Transformer { - val labels = perRunCaches.newMap[Symbol, Symbol]() - var method: Symbol = _ - var ctx: Context = _ - - def apply(ctx: Context, t: Tree) = { - this.method = ctx.method.symbol - this.ctx = ctx - transform(t) - } - - override def transform(t: Tree): Tree = { - val sym = t.symbol - def getLabel(pos: Position, name: Name) = - labels.getOrElseUpdate(sym, - method.newLabel(unit.freshTermName(name.toString), sym.pos) setInfo sym.tpe - ) - - t match { - case t @ Apply(_, args) if sym.isLabel && !boundLabels(sym) => - val newSym = getLabel(sym.pos, sym.name) - Apply(global.gen.mkAttributedRef(newSym), transformTrees(args)) setPos t.pos setType t.tpe - - case t @ LabelDef(name, params, rhs) => - val newSym = getLabel(t.pos, name) - val tree = treeCopy.LabelDef(t, newSym.name, params, transform(rhs)) - tree.symbol = newSym - - val pair = (newSym -> (new Label(newSym) setParams (params map (_.symbol)))) - log("Added " + pair + " to labels.") - ctx.labels += pair - ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false))) - - tree - - case _ => super.transform(t) - } - } - } - - /////////////////////// Context //////////////////////////////// - - sealed abstract class Cleanup(val value: AnyRef) { - def contains(x: AnyRef) = value == x - } - case class MonitorRelease(m: Local) extends Cleanup(m) { } - case class Finalizer(f: Tree, ctx: Context) extends Cleanup (f) { } - - def duplicateFinalizer(boundLabels: Set[Symbol], targetCtx: Context, finalizer: Tree) = { - (new DuplicateLabels(boundLabels))(targetCtx, finalizer) - } - - def savingCleanups[T](ctx: Context)(body: => T): T = { - val saved = ctx.cleanups - try body - finally ctx.cleanups = saved - } - - /** - * The Context class keeps information relative to the current state - * in code generation - */ - class Context { - /** The current package. */ - var packg: Name = _ - - /** The current class. */ - var clazz: IClass = _ - - /** The current method. */ - var method: IMethod = _ - - /** The current basic block. */ - var bb: BasicBlock = _ - - /** Map from label symbols to label objects. */ - var labels = perRunCaches.newMap[Symbol, Label]() - - /** Current method definition. */ - var defdef: DefDef = _ - - /** current exception handlers */ - var handlers: List[ExceptionHandler] = Nil - - /** The current monitors or finalizers, to be cleaned up upon `return`. */ - var cleanups: List[Cleanup] = Nil - - /** The exception handlers we are currently generating code for */ - var currentExceptionHandlers: List[ExceptionHandler] = Nil - - /** The current local variable scope. */ - var scope: Scope = EmptyScope - - var handlerCount = 0 - - override def toString = - s"package $packg { class $clazz { def $method { bb=$bb } } }" - - def loadException(ctx: Context, exh: ExceptionHandler, pos: Position) = { - debuglog("Emitting LOAD_EXCEPTION for class: " + exh.loadExceptionClass) - ctx.bb.emit(LOAD_EXCEPTION(exh.loadExceptionClass) setPos pos, pos) - } - - def this(other: Context) = { - this() - this.packg = other.packg - this.clazz = other.clazz - this.method = other.method - this.bb = other.bb - this.labels = other.labels - this.defdef = other.defdef - this.handlers = other.handlers - this.handlerCount = other.handlerCount - this.cleanups = other.cleanups - this.currentExceptionHandlers = other.currentExceptionHandlers - this.scope = other.scope - } - - def setPackage(p: Name): this.type = { - this.packg = p - this - } - - def setClass(c: IClass): this.type = { - this.clazz = c - this - } - - def setMethod(m: IMethod): this.type = { - this.method = m - this - } - - def setBasicBlock(b: BasicBlock): this.type = { - this.bb = b - this - } - - def enterSynchronized(monitor: Local): this.type = { - cleanups = MonitorRelease(monitor) :: cleanups - this - } - - def exitSynchronized(monitor: Local): this.type = { - assert(cleanups.head contains monitor, - "Bad nesting of cleanup operations: " + cleanups + " trying to exit from monitor: " + monitor) - cleanups = cleanups.tail - this - } - - def addFinalizer(f: Tree, ctx: Context): this.type = { - cleanups = Finalizer(f, ctx) :: cleanups - this - } - - /** Prepare a new context upon entry into a method. - */ - def enterMethod(m: IMethod, d: DefDef): Context = { - val ctx1 = new Context(this) setMethod(m) - ctx1.labels = mutable.HashMap() - ctx1.method.code = new Code(m) - ctx1.bb = ctx1.method.startBlock - ctx1.defdef = d - ctx1.scope = EmptyScope - ctx1.enterScope() - ctx1 - } - - /** Return a new context for a new basic block. */ - def newBlock(): Context = { - val block = method.code.newBlock() - handlers foreach (_ addCoveredBlock block) - currentExceptionHandlers foreach (_ addBlock block) - block.varsInScope.clear() - block.varsInScope ++= scope.varsInScope - new Context(this) setBasicBlock block - } - - def enterScope() { - scope = new Scope(scope) - } - - def exitScope() { - if (bb.nonEmpty) { - scope.locals foreach { lv => bb.emit(SCOPE_EXIT(lv)) } - } - scope = scope.outer - } - - /** Create a new exception handler and adds it in the list - * of current exception handlers. All new blocks will be - * 'covered' by this exception handler (in addition to the - * previously active handlers). - */ - private def newExceptionHandler(cls: Symbol, pos: Position): ExceptionHandler = { - handlerCount += 1 - val exh = new ExceptionHandler(method, newTermNameCached("" + handlerCount), cls, pos) - method.addHandler(exh) - handlers = exh :: handlers - debuglog("added handler: " + exh) - - exh - } - - /** Add an active exception handler in this context. It will cover all new basic blocks - * created from now on. */ - private def addActiveHandler(exh: ExceptionHandler) { - handlerCount += 1 - handlers = exh :: handlers - debuglog("added handler: " + exh) - } - - /** Return a new context for generating code for the given - * exception handler. - */ - private def enterExceptionHandler(exh: ExceptionHandler): Context = { - currentExceptionHandlers ::= exh - val ctx = newBlock() - exh.setStartBlock(ctx.bb) - ctx - } - - def endHandler() { - currentExceptionHandlers = currentExceptionHandlers.tail - } - - /** Clone the current context */ - def dup: Context = new Context(this) - - /** Make a fresh local variable. It ensures the 'name' is unique. */ - def makeLocal(pos: Position, tpe: Type, name: String): Local = { - val sym = method.symbol.newVariable(unit.freshTermName(name), pos, Flags.SYNTHETIC) setInfo tpe - this.method.addLocal(new Local(sym, toTypeKind(tpe), false)) - } - - - /** - * Generate exception handlers for the body. Body is evaluated - * with a context where all the handlers are active. Handlers are - * evaluated in the 'outer' context. - * - * It returns the resulting context, with the same active handlers as - * before the call. Use it like: - * - * ` ctx.Try( ctx => { - * ctx.bb.emit(...) // protected block - * }, (ThrowableClass, - * ctx => { - * ctx.bb.emit(...); // exception handler - * }), (AnotherExceptionClass, - * ctx => {... - * } ))` - * - * The resulting structure will look something like - * - * outer: - * // this 'useless' jump will be removed later, - * // for now it separates the try body's blocks from previous - * // code since the try body needs its own exception handlers - * JUMP body - * - * body: - * [ try body ] - * JUMP normalExit - * - * catch[i]: - * [ handler[i] body ] - * JUMP normalExit - * - * catchAll: - * STORE exception - * [ finally body ] - * THROW exception - * - * normalExit: - * [ finally body ] - * - * each catch[i] will cover body. catchAll will cover both body and each catch[i] - * Additional finally copies are created on the emission of every RETURN in the try body and exception handlers. - * - * This could result in unreachable code which has to be cleaned up later, e.g. if the try and all the exception - * handlers always end in RETURN then there will be no "normal" flow out of the try/catch/finally. - * Later reachability analysis will remove unreachable code. - */ - def Try(body: Context => Context, - handlers: List[(Symbol, TypeKind, Context => Context)], - finalizer: Tree, - tree: Tree) = { - - val outerCtx = this.dup // context for generating exception handlers, covered by the catch-all finalizer - val finalizerCtx = this.dup // context for generating finalizer handler - val normalExitCtx = outerCtx.newBlock() // context where flow will go on a "normal" (non-return, non-throw) exit from a try or catch handler - var normalExitReachable = false - var tmp: Local = null - val kind = toTypeKind(tree.tpe) - val guardResult = kind != UNIT && mayCleanStack(finalizer) - // we need to save bound labels before any code generation is performed on - // the current context (otherwise, any new labels in the finalizer that need to - // be duplicated would be incorrectly considered bound -- see #2850). - val boundLabels: Set[Symbol] = Set.empty ++ labels.keySet - - if (guardResult) { - tmp = this.makeLocal(tree.pos, tree.tpe, "tmp") - } - - def emitFinalizer(ctx: Context): Context = if (!finalizer.isEmpty) { - val ctx1 = finalizerCtx.dup.newBlock() - ctx1.bb killIf ctx.bb.ignore - ctx.bb.closeWith(JUMP(ctx1.bb)) - - if (guardResult) { - ctx1.bb.emit(STORE_LOCAL(tmp)) - val ctx2 = genLoad(duplicateFinalizer(boundLabels, ctx1, finalizer), ctx1, UNIT) - ctx2.bb.emit(LOAD_LOCAL(tmp)) - ctx2 - } else - genLoad(duplicateFinalizer(boundLabels, ctx1, finalizer), ctx1, UNIT) - } else ctx - - - // Generate the catch-all exception handler that deals with uncaught exceptions coming - // from the try or exception handlers. It catches the exception, runs the finally code, then rethrows - // the exception - if (settings.YdisableUnreachablePrevention || !outerCtx.bb.ignore) { - if (finalizer != EmptyTree) { - val exh = outerCtx.newExceptionHandler(NoSymbol, finalizer.pos) // finalizer covers exception handlers - this.addActiveHandler(exh) // .. and body as well - val exhStartCtx = finalizerCtx.enterExceptionHandler(exh) - exhStartCtx.bb killIf outerCtx.bb.ignore - val exception = exhStartCtx.makeLocal(finalizer.pos, ThrowableTpe, "exc") - loadException(exhStartCtx, exh, finalizer.pos) - exhStartCtx.bb.emit(STORE_LOCAL(exception)) - val exhEndCtx = genLoad(finalizer, exhStartCtx, UNIT) - exhEndCtx.bb.emit(LOAD_LOCAL(exception)) - exhEndCtx.bb.closeWith(THROW(ThrowableClass)) - exhEndCtx.bb.enterIgnoreMode() - finalizerCtx.endHandler() - } - - // Generate each exception handler - for ((sym, kind, handler) <- handlers) { - val exh = this.newExceptionHandler(sym, tree.pos) - val exhStartCtx = outerCtx.enterExceptionHandler(exh) - exhStartCtx.bb killIf outerCtx.bb.ignore - exhStartCtx.addFinalizer(finalizer, finalizerCtx) - loadException(exhStartCtx, exh, tree.pos) - val exhEndCtx = handler(exhStartCtx) - normalExitReachable ||= !exhEndCtx.bb.ignore - exhEndCtx.bb.closeWith(JUMP(normalExitCtx.bb)) - outerCtx.endHandler() - } - } - - val bodyCtx = this.newBlock() - bodyCtx.bb killIf outerCtx.bb.ignore - if (finalizer != EmptyTree) - bodyCtx.addFinalizer(finalizer, finalizerCtx) - - val bodyEndCtx = body(bodyCtx) - - outerCtx.bb.closeWith(JUMP(bodyCtx.bb)) - - normalExitReachable ||= !bodyEndCtx.bb.ignore - normalExitCtx.bb killUnless normalExitReachable - bodyEndCtx.bb.closeWith(JUMP(normalExitCtx.bb)) - - emitFinalizer(normalExitCtx) - } - } - } - - /** - * Represent a label in the current method code. In order - * to support forward jumps, labels can be created without - * having a designated target block. They can later be attached - * by calling `anchor`. - */ - class Label(val symbol: Symbol) { - var anchored = false - var block: BasicBlock = _ - var params: List[Symbol] = _ - - private var toPatch: List[Instruction] = Nil - - /** Fix this label to the given basic block. */ - def anchor(b: BasicBlock): Label = { - assert(!anchored, "Cannot anchor an already anchored label!") - anchored = true - this.block = b - this - } - - def setParams(p: List[Symbol]): Label = { - assert(params eq null, "Cannot set label parameters twice!") - params = p - this - } - - /** Add an instruction that refers to this label. */ - def addCallingInstruction(i: Instruction) = - toPatch = i :: toPatch - - /** - * Patch the code by replacing pseudo call instructions with - * jumps to the given basic block. - */ - def patch(code: Code) { - val map = mapFrom(toPatch)(patch) - code.blocks foreach (_ subst map) - } - - /** - * Return the patched instruction. If the given instruction - * jumps to this label, replace it with the basic block. Otherwise, - * return the same instruction. Conditional jumps have more than one - * label, so they are replaced only if all labels are anchored. - */ - def patch(instr: Instruction): Instruction = { - assert(anchored, "Cannot patch until this label is anchored: " + this) - - instr match { - case PJUMP(self) - if (self == this) => JUMP(block) - - case PCJUMP(self, failure, cond, kind) - if (self == this && failure.anchored) => - CJUMP(block, failure.block, cond, kind) - - case PCJUMP(success, self, cond, kind) - if (self == this && success.anchored) => - CJUMP(success.block, block, cond, kind) - - case PCZJUMP(self, failure, cond, kind) - if (self == this && failure.anchored) => - CZJUMP(block, failure.block, cond, kind) - - case PCZJUMP(success, self, cond, kind) - if (self == this && success.anchored) => - CZJUMP(success.block, block, cond, kind) - - case _ => instr - } - } - - override def toString() = symbol.toString() - } - - ///////////////// Fake instructions ////////////////////////// - - /** - * Pseudo jump: it takes a Label instead of a basic block. - * It is used temporarily during code generation. It is replaced - * by a real JUMP instruction when all labels are resolved. - */ - abstract class PseudoJUMP(label: Label) extends Instruction { - override def toString = s"PJUMP(${label.symbol})" - override def consumed = 0 - override def produced = 0 - - // register with the given label - if (!label.anchored) - label.addCallingInstruction(this) - } - - case class PJUMP(whereto: Label) extends PseudoJUMP(whereto) - - case class PCJUMP(success: Label, failure: Label, cond: TestOp, kind: TypeKind) - extends PseudoJUMP(success) { - override def toString(): String = - "PCJUMP (" + kind + ") " + success.symbol.simpleName + - " : " + failure.symbol.simpleName - - if (!failure.anchored) - failure.addCallingInstruction(this) - } - - case class PCZJUMP(success: Label, failure: Label, cond: TestOp, kind: TypeKind) - extends PseudoJUMP(success) { - override def toString(): String = - "PCZJUMP (" + kind + ") " + success.symbol.simpleName + - " : " + failure.symbol.simpleName - - if (!failure.anchored) - failure.addCallingInstruction(this) - } - - /** Local variable scopes. Keep track of line numbers for debugging info. */ - class Scope(val outer: Scope) { - val locals: ListBuffer[Local] = new ListBuffer - - def add(l: Local) = locals += l - - /** Return all locals that are in scope. */ - def varsInScope: Buffer[Local] = outer.varsInScope.clone() ++= locals - - override def toString() = locals.mkString(outer.toString + "[", ", ", "]") - } - - object EmptyScope extends Scope(null) { - override def toString() = "[]" - override def varsInScope: Buffer[Local] = new ListBuffer - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodeCheckers.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodeCheckers.scala deleted file mode 100644 index 0f17b5d694..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/ICodeCheckers.scala +++ /dev/null @@ -1,711 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -import scala.collection.mutable -import scala.collection.mutable.ListBuffer - -abstract class ICodeCheckers { - val global: Global - import global._ - - /** <p> - * This class performs a set of checks similar to what the bytecode - * verifier does. For each basic block, it checks that: - * </p> - * <ul> - * <li> - * for primitive operations: the type and number of operands match - * the type of the operation - * </li> - * <li> - * for method calls: the method exists in the type of the receiver - * and the number and type of arguments match the declared type of - * the method. - * </li> - * <li> - * for object creation: the constructor can be called. - * </li> - * <li> - * for load/stores: the field/local/param exists and the type - * of the value matches that of the target. - * </li> - * </ul> - * <p> - * For a control flow graph it checks that type stacks at entry to - * each basic block 'agree': - * </p> - * <ul> - * <li>they have the same length</li> - * <li>there exists a lub for all types at the same position in stacks.</li> - * </ul> - * - * @author Iulian Dragos - * @version 1.0, 06/09/2005 - * - * @todo Better checks for `MONITOR_ENTER/EXIT` - * Better checks for local var initializations - * - * @todo Iulian says: I think there's some outdated logic in the checker. - * The issue with exception handlers being special for least upper - * bounds pointed out some refactoring in the lattice class. Maybe - * a worthwhile refactoring would be to make the checker use the - * DataFlowAnalysis class, and use the lattice trait. In the - * implementation of LUB, there's a flag telling if one of the - * successors is 'exceptional'. The inliner is using this mechanism. - */ - class ICodeChecker { - import icodes._ - import opcodes._ - - var clasz: IClass = _ - var method: IMethod = _ - var code: Code = _ - - val in: mutable.Map[BasicBlock, TypeStack] = perRunCaches.newMap() - val out: mutable.Map[BasicBlock, TypeStack] = perRunCaches.newMap() - val emptyStack = new TypeStack() { - override def toString = "<empty>" - } - - /** The presence of emptyStack means that path has not yet been checked - * (and may not be empty). - */ - def notChecked(ts: TypeStack) = ts eq emptyStack - def initMaps(bs: Seq[BasicBlock]): Unit = { - in.clear() - out.clear() - bs foreach { b => - in(b) = emptyStack - out(b) = emptyStack - } - } - - /** A wrapper to route log messages to debug output also. - */ - def logChecker(msg: String) = { - log(msg) - checkerDebug(msg) - } - - def checkICodes(): Unit = { - if (settings.verbose) - println("[[consistency check at the beginning of phase " + globalPhase.name + "]]") - classes.values foreach check - } - - private def posStr(p: Position) = - if (p.isDefined) p.line.toString else "<??>" - - private def indent(s: String, prefix: String): String = { - val lines = s split "\\n" - lines map (prefix + _) mkString "\n" - } - - /** Only called when m1 < m2, so already known that (m1 ne m2). - */ - private def isConflict(m1: IMember, m2: IMember, canOverload: Boolean) = ( - (m1.symbol.name == m2.symbol.name) && - (!canOverload || (m1.symbol.tpe =:= m2.symbol.tpe)) - ) - - def check(cls: IClass) { - logChecker("\n<<-- Checking class " + cls + " -->>") - clasz = cls - - for (f1 <- cls.fields ; f2 <- cls.fields ; if f1 < f2) - if (isConflict(f1, f2, canOverload = false)) - icodeError("Repetitive field name: " + f1.symbol.fullName) - - for (m1 <- cls.methods ; m2 <- cls.methods ; if m1 < m2) - if (isConflict(m1, m2, canOverload = true)) - icodeError("Repetitive method: " + m1.symbol.fullName) - - clasz.methods foreach check - } - - def check(m: IMethod) { - logChecker("\n<< Checking method " + m.symbol.name + " >>") - method = m - if (!m.isAbstractMethod) - check(m.code) - } - - def check(c: Code) { - val worklist = new ListBuffer[BasicBlock] - def append(elems: List[BasicBlock]) = - worklist ++= (elems filterNot (worklist contains _)) - - code = c - worklist += c.startBlock - initMaps(c.blocks) - - while (worklist.nonEmpty) { - val block = worklist remove 0 - val output = check(block, in(block)) - if (output != out(block) || notChecked(out(block))) { - if (block.successors.nonEmpty) - logChecker("** Output change for %s: %s -> %s".format(block, out(block), output)) - - out(block) = output - append(block.successors) - block.successors foreach meet - } - } - } - - /** - * Apply the meet operator of the stack lattice on bl's predecessors. - * :-). Compute the input to bl by checking that all stacks have the - * same length, and taking the lub of types at the same positions. - */ - def meet(bl: BasicBlock) { - val preds = bl.predecessors - - def hasNothingType(s: TypeStack) = s.nonEmpty && (s.head == NothingReference) - - /* XXX workaround #1: one stack empty, the other has BoxedUnit. - * One example where this arises is: - * - * def f(b: Boolean): Unit = synchronized { if (b) () } - */ - def allUnits(s: TypeStack) = s.types forall (_ == BoxedUnitReference) - - def ifAthenB[T](f: T => Boolean): PartialFunction[(T, T), T] = { - case (x1, x2) if f(x1) => x2 - case (x1, x2) if f(x2) => x1 - } - - /* XXX workaround #2: different stacks heading into an exception - * handler which will clear them anyway. Examples where it arises: - * - * var bippy: Int = synchronized { if (b) 5 else 10 } - */ - def isHandlerBlock() = bl.exceptionHandlerStart - - def meet2(s1: TypeStack, s2: TypeStack): TypeStack = { - def workaround(msg: String) = { - checkerDebug(msg + ": " + method + " at block " + bl) - checkerDebug(" s1: " + s1) - checkerDebug(" s2: " + s2) - new TypeStack() - } - def incompatibleString = ( - "Incompatible stacks: " + s1 + " and " + s2 + " in " + method + " at entry to block " + bl.label + ":\n" + - indent(bl.predContents, "// ") + - indent(bl.succContents, "// ") + - indent(bl.blockContents, "// ") - ) - - val f: ((TypeStack, TypeStack)) => TypeStack = { - ifAthenB(notChecked) orElse ifAthenB(hasNothingType) orElse { - case (s1: TypeStack, s2: TypeStack) => - if (s1.length != s2.length) { - if (allUnits(s1) && allUnits(s2)) - workaround("Ignoring mismatched boxed units") - else if (isHandlerBlock()) - workaround("Ignoring mismatched stacks entering exception handler") - else - throw new CheckerException(incompatibleString) - } - else { - val newStack: TypeStack = try { - new TypeStack((s1.types, s2.types).zipped map lub) - } catch { - case t: Exception => - checkerDebug(t.toString + ": " + s1.types.toString + " vs " + s2.types.toString) - new TypeStack(s1.types) - } - if (newStack.isEmpty || s1.types == s2.types) () // not interesting to report - else checkerDebug("Checker created new stack:\n (%s, %s) => %s".format(s1, s2, newStack)) - - newStack - } - } - } - - f((s1, s2)) - } - - if (preds.nonEmpty) { - in(bl) = (preds map out.apply) reduceLeft meet2 - log("Input changed for block: " + bl +" to: " + in(bl)) - } - } - - private var instruction: Instruction = null - private var basicBlock: BasicBlock = null - private var stringConcatDepth = 0 - private def stringConcatIndent() = " " * stringConcatDepth - private def currentInstrString: String = { - val (indent, str) = this.instruction match { - case CALL_PRIMITIVE(StartConcat) => - val x = stringConcatIndent() - stringConcatDepth += 1 - (x, "concat(") - case CALL_PRIMITIVE(EndConcat) => - if (stringConcatDepth > 0) { - stringConcatDepth -= 1 - (stringConcatIndent(), ") // end concat") - } - else ("", "") - case _ => - (stringConcatIndent(), this.instruction match { - case CALL_PRIMITIVE(StringConcat(el)) => "..." - case null => "null" - case cm @ CALL_METHOD(_, _) => if (clasz.symbol == cm.hostClass) cm.toShortString else cm.toString - case x => x.toString - }) - } - indent + str - } - /** A couple closure creators to reduce noise in the output: when multiple - * items are pushed or popped, this lets us print something short and sensible - * for those beyond the first. - */ - def mkInstrPrinter(f: Int => String): () => String = { - var counter = -1 - val indent = stringConcatIndent() - () => { - counter += 1 - if (counter == 0) currentInstrString - else indent + f(counter) - } - } - def defaultInstrPrinter: () => String = mkInstrPrinter(_ => "\"\"\"") - - /** - * Check the basic block to be type correct and return the - * produced type stack. - */ - def check(b: BasicBlock, initial: TypeStack): TypeStack = { - this.basicBlock = b - - logChecker({ - val prefix = "** Checking " + b.fullString - - if (initial.isEmpty) prefix - else prefix + " with initial stack " + initial.types.mkString("[", ", ", "]") - }) - - val stack = new TypeStack(initial) - def checkStack(len: Int) { - if (stack.length < len) - ICodeChecker.this.icodeError("Expected at least " + len + " elements on the stack", stack) - } - - def sizeString(push: Boolean) = { - val arrow = if (push) "-> " else "<- " - val sp = " " * stack.length - - sp + stack.length + arrow - } - def printStackString(isPush: Boolean, value: TypeKind, instrString: String) = { - val pushString = if (isPush) "+" else "-" - val posString = posStr(this.instruction.pos) - - checkerDebug("%-70s %-4s %s %s".format(sizeString(isPush) + value, posString, pushString, instrString)) - } - def _popStack: TypeKind = { - if (stack.isEmpty) { - icodeError("Popped empty stack in " + b.fullString + ", throwing a Unit") - return UNIT - } - stack.pop - } - def popStackN(num: Int, instrFn: () => String = defaultInstrPrinter) = { - List.range(0, num) map { _ => - val res = _popStack - printStackString(isPush = false, res, instrFn()) - res - } - } - def pushStackN(xs: Seq[TypeKind], instrFn: () => String) = { - xs foreach { x => - stack push x - printStackString(isPush = true, x, instrFn()) - } - } - - def popStack = { checkStack(1) ; (popStackN(1): @unchecked) match { case List(x) => x } } - def popStack2 = { checkStack(2) ; (popStackN(2): @unchecked) match { case List(x, y) => (x, y) } } - def popStack3 = { checkStack(3) ; (popStackN(3): @unchecked) match { case List(x, y, z) => (x, y, z) } } - - /* Called by faux instruction LOAD_EXCEPTION to wipe out the stack. */ - def clearStack() = { - if (stack.nonEmpty) - logChecker("Wiping out the " + stack.length + " element stack for exception handler: " + stack) - - 1 to stack.length foreach (_ => popStack) - } - - def pushStack(xs: TypeKind*): Unit = { - pushStackN(xs filterNot (_ == UNIT), defaultInstrPrinter) - } - - def typeError(k1: TypeKind, k2: TypeKind) { - icodeError("\n expected: " + k1 + "\n found: " + k2) - } - def isSubtype(k1: TypeKind, k2: TypeKind) = (k1 isAssignabledTo k2) || { - import platform.isMaybeBoxed - - (k1, k2) match { - case (REFERENCE(_), REFERENCE(_)) if k1.isInterfaceType || k2.isInterfaceType => - logChecker("Considering %s <:< %s because at least one is an interface".format(k1, k2)) - true - case (REFERENCE(cls1), REFERENCE(cls2)) if isMaybeBoxed(cls1) || isMaybeBoxed(cls2) => - logChecker("Considering %s <:< %s because at least one might be a boxed primitive".format(cls1, cls2)) - true - case _ => - false - } - } - - def subtypeTest(k1: TypeKind, k2: TypeKind): Unit = - if (isSubtype(k1, k2)) () - else typeError(k2, k1) - - for (instr <- b) { - this.instruction = instr - - def checkLocal(local: Local) { - if ((method lookupLocal local.sym.name).isEmpty) - icodeError(s" $local is not defined in method $method") - } - def checkField(obj: TypeKind, field: Symbol): Unit = obj match { - case REFERENCE(sym) => - if (sym.info.member(field.name) == NoSymbol) - icodeError(" " + field + " is not defined in class " + clasz) - case _ => - icodeError(" expected reference type, but " + obj + " found") - } - - /* Checks that tpe is a subtype of one of the allowed types */ - def checkType(tpe: TypeKind, allowed: TypeKind*) = ( - if (allowed exists (k => isSubtype(tpe, k))) () - else icodeError(tpe + " is not one of: " + allowed.mkString("{ ", ", ", " }")) - ) - def checkNumeric(tpe: TypeKind) = - checkType(tpe, BYTE, CHAR, SHORT, INT, LONG, FLOAT, DOUBLE) - - /* Checks that the 2 topmost elements on stack are of the kind TypeKind. */ - def checkBinop(kind: TypeKind) { - val (a, b) = popStack2 - checkType(a, kind) - checkType(b, kind) - } - - /* Check that arguments on the stack match method params. */ - def checkMethodArgs(method: Symbol) { - val params = method.info.paramTypes - checkStack(params.length) - ( - popStackN(params.length, mkInstrPrinter(num => "<arg" + num + ">")), - params.reverse map toTypeKind).zipped foreach ((x, y) => checkType(x, y) - ) - } - - /* Checks that the object passed as receiver has a method - * `method` and that it is callable from the current method. - */ - def checkMethod(receiver: TypeKind, method: Symbol) = - receiver match { - case REFERENCE(sym) => - checkBool(sym.info.member(method.name) != NoSymbol, - "Method " + method + " does not exist in " + sym.fullName) - if (method.isPrivate) - checkBool(method.owner == clasz.symbol, - "Cannot call private method of " + method.owner.fullName - + " from " + clasz.symbol.fullName) - else if (method.isProtected) { - val isProtectedOK = ( - (clasz.symbol isSubClass method.owner) || - (clasz.symbol.typeOfThis.typeSymbol isSubClass method.owner) // see pos/bug780.scala - ) - - checkBool(isProtectedOK, - "Cannot call protected method of " + method.owner.fullName - + " from " + clasz.symbol.fullName) - } - - case ARRAY(_) => - checkBool(receiver.toType.member(method.name) != NoSymbol, - "Method " + method + " does not exist in " + receiver) - - case t => - icodeError("Not a reference type: " + t) - } - - def checkBool(cond: Boolean, msg: String) = - if (!cond) icodeError(msg) - - if (settings.debug) { - log("PC: " + instr) - log("stack: " + stack) - log("================") - } - instr match { - case THIS(clasz) => - pushStack(toTypeKind(clasz.tpe)) - - case CONSTANT(const) => - pushStack(toTypeKind(const.tpe)) - - case LOAD_ARRAY_ITEM(kind) => - popStack2 match { - case (INT, ARRAY(elem)) => - subtypeTest(elem, kind) - pushStack(elem) - case (a, b) => - icodeError(" expected an INT and an array reference, but " + - a + ", " + b + " found") - } - - case LOAD_LOCAL(local) => - checkLocal(local) - pushStack(local.kind) - - case LOAD_FIELD(field, isStatic) => - // the symbol's owner should contain its field, but - // this is already checked by the type checker, no need - // to redo that here - if (isStatic) () - else checkField(popStack, field) - - pushStack(toTypeKind(field.tpe)) - - case LOAD_MODULE(module) => - checkBool((module.isModule || module.isModuleClass), - "Expected module: " + module + " flags: " + module.flagString) - pushStack(toTypeKind(module.tpe)) - - case STORE_THIS(kind) => - val actualType = popStack - if (actualType.isReferenceType) subtypeTest(actualType, kind) - else icodeError("Expected this reference but found: " + actualType) - - case STORE_ARRAY_ITEM(kind) => - popStack3 match { - case (k, INT, ARRAY(elem)) => - subtypeTest(k, kind) - subtypeTest(k, elem) - case (a, b, c) => - icodeError(" expected and array reference, and int and " + kind + - " but " + a + ", " + b + ", " + c + " found") - } - - case STORE_LOCAL(local) => - checkLocal(local) - val actualType = popStack - if (local.kind != NullReference) - subtypeTest(actualType, local.kind) - - case STORE_FIELD(field, true) => // static - val fieldType = toTypeKind(field.tpe) - val actualType = popStack - subtypeTest(actualType, fieldType) - - case STORE_FIELD(field, false) => // not static - val (value, obj) = popStack2 - checkField(obj, field) - val fieldType = toTypeKind(field.tpe) - if (fieldType == NullReference) () - else subtypeTest(value, fieldType) - - case CALL_PRIMITIVE(primitive) => - checkStack(instr.consumed) - primitive match { - case Negation(kind) => - checkType(kind, BOOL, BYTE, CHAR, SHORT, INT, LONG, FLOAT, DOUBLE) - checkType(popStack, kind) - pushStack(kind) - - case Test(op, kind, zero) => - if (zero) checkType(popStack, kind) - else checkBinop(kind) - - pushStack(BOOL) - - case Comparison(op, kind) => - checkNumeric(kind) - checkBinop(kind) - pushStack(INT) - - case Arithmetic(op, kind) => - checkNumeric(kind) - if (op == NOT) - checkType(popStack, kind) - else - checkBinop(kind) - pushStack(kind) - - case Logical(op, kind) => - checkType(kind, BOOL, BYTE, CHAR, SHORT, INT, LONG) - checkBinop(kind) - pushStack(kind) - - case Shift(op, kind) => - checkType(kind, BYTE, CHAR, SHORT, INT, LONG) - val (a, b) = popStack2 - checkType(a, INT) - checkType(b, kind) - pushStack(kind) - - case Conversion(src, dst) => - checkNumeric(src) - checkNumeric(dst) - checkType(popStack, src) - pushStack(dst) - - case ArrayLength(kind) => - popStack match { - case ARRAY(elem) => checkType(elem, kind) - case arr => icodeError(" array reference expected, but " + arr + " found") - } - pushStack(INT) - - case StartConcat => - pushStack(ConcatClass) - - case EndConcat => - checkType(popStack, ConcatClass) - pushStack(StringReference) - - case StringConcat(el) => - checkType(popStack, el) - checkType(popStack, ConcatClass) - pushStack(ConcatClass) - } - - case CALL_METHOD(method, style) => - // PP to ID: I moved the if (!method.isConstructor) check to cover all - // the styles to address checker failure. Can you confirm if the change - // was correct? If I remember right it's a matter of whether some brand - // of supercall should leave a value on the stack, and I know there is some - // trickery performed elsewhere regarding this. - val paramCount = method.info.paramTypes.length match { - case x if style.hasInstance => x + 1 - case x => x - } - if (style == Static(onInstance = true)) - checkBool(method.isPrivate || method.isConstructor, "Static call to non-private method.") - - checkStack(paramCount) - checkMethodArgs(method) - if (style.hasInstance) - checkMethod(popStack, method) - if (!method.isConstructor) - pushStack(toTypeKind(method.info.resultType)) - - case NEW(kind) => - pushStack(kind) - - case CREATE_ARRAY(elem, dims) => - checkStack(dims) - stack.pop(dims) foreach (checkType(_, INT)) - pushStack(ARRAY(elem)) - - case IS_INSTANCE(tpe) => - val ref = popStack - checkBool(!ref.isValueType, "IS_INSTANCE on primitive type: " + ref) - checkBool(!tpe.isValueType, "IS_INSTANCE on primitive type: " + tpe) - pushStack(BOOL) - - case CHECK_CAST(tpe) => - val ref = popStack - checkBool(!ref.isValueType, "CHECK_CAST to primitive type: " + ref) - checkBool(!tpe.isValueType, "CHECK_CAST to primitive type: " + tpe) - pushStack(tpe) - - case SWITCH(tags, labels) => - checkType(popStack, INT) - checkBool(tags.length == labels.length - 1, - "The number of tags and labels does not coincide.") - checkBool(labels forall (b => code.blocks contains b), - "Switch target cannot be found in code.") - - case JUMP(whereto) => - checkBool(code.blocks contains whereto, - "Jump to non-existant block " + whereto) - - case CJUMP(success, failure, cond, kind) => - checkBool(code.blocks contains success, - "Jump to non-existant block " + success) - checkBool(code.blocks contains failure, - "Jump to non-existant block " + failure) - checkBinop(kind) - - case CZJUMP(success, failure, cond, kind) => - checkBool(code.blocks contains success, - "Jump to non-existant block " + success) - checkBool(code.blocks contains failure, - "Jump to non-existant block " + failure) - checkType(popStack, kind) - - case RETURN(UNIT) => () - case RETURN(kind) => - val top = popStack - if (kind.isValueType) checkType(top, kind) - else checkBool(!top.isValueType, "" + kind + " is a reference type, but " + top + " is not") - - case THROW(clasz) => - checkType(popStack, toTypeKind(clasz.tpe)) - pushStack(NothingReference) - - case DROP(kind) => - checkType(popStack, kind) - - case DUP(kind) => - val top = popStack - checkType(top, kind) - pushStack(top) - pushStack(top) - - case MONITOR_ENTER() => - checkBool(popStack.isReferenceType, "MONITOR_ENTER on non-reference type") - - case MONITOR_EXIT() => - checkBool(popStack.isReferenceType, "MONITOR_EXIT on non-reference type") - - case BOX(kind) => - checkType(popStack, kind) - pushStack(REFERENCE(definitions.boxedClass(kind.toType.typeSymbol))) - - case UNBOX(kind) => - popStack - pushStack(kind) - - case LOAD_EXCEPTION(clasz) => - clearStack() - pushStack(REFERENCE(clasz)) - - case SCOPE_ENTER(_) | SCOPE_EXIT(_) => - () - - case _ => - abort("Unknown instruction: " + instr) - } - } - stack - } - - //////////////// Error reporting ///////////////////////// - - def icodeError(msg: String) { - ICodeCheckers.this.global.warning( - "!! ICode checker fatality in " + method + - "\n at: " + basicBlock.fullString + - "\n error message: " + msg - ) - } - - def icodeError(msg: String, stack: TypeStack) { - icodeError(msg + "\n type stack: " + stack) - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala deleted file mode 100644 index 10f0c6ee00..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala +++ /dev/null @@ -1,129 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -import java.io.PrintWriter -import analysis.{ Liveness, ReachingDefinitions } -import scala.tools.nsc.symtab.classfile.ICodeReader -import scala.reflect.io.AbstractFile - -/** Glue together ICode parts. - * - * @author Iulian Dragos - */ -abstract class ICodes extends AnyRef - with Members - with BasicBlocks - with Opcodes - with TypeStacks - with TypeKinds - with ExceptionHandlers - with Primitives - with Linearizers - with Printers - with Repository -{ - val global: Global - import global.{ log, definitions, settings, perRunCaches, devWarning } - - /** The ICode representation of classes */ - val classes = perRunCaches.newMap[global.Symbol, IClass]() - - /** Debugging flag */ - def shouldCheckIcode = settings.check contains global.genicode.phaseName - def checkerDebug(msg: String) = if (shouldCheckIcode && global.settings.debug) println(msg) - - /** The ICode linearizer. */ - val linearizer: Linearizer = settings.Xlinearizer.value match { - case "rpo" => new ReversePostOrderLinearizer() - case "dfs" => new DepthFirstLinerizer() - case "normal" => new NormalLinearizer() - case "dump" => new DumpLinearizer() - case x => global.abort("Unknown linearizer: " + x) - } - - def newTextPrinter() = - new TextPrinter(new PrintWriter(Console.out, true), new DumpLinearizer) - - /** Have to be careful because dump calls around, possibly - * re-entering methods which initiated the dump (like foreach - * in BasicBlocks) which leads to the icode output olympics. - */ - private var alreadyDumping = false - - /** Print all classes and basic blocks. Used for debugging. */ - - def dumpClassesAndAbort(msg: String): Nothing = { - if (alreadyDumping) global.abort(msg) - else alreadyDumping = true - - Console.println(msg) - val printer = newTextPrinter() - classes.values foreach printer.printClass - global.abort(msg) - } - - def dumpMethodAndAbort(m: IMethod, msg: String): Nothing = { - Console.println("Fatal bug in inlinerwhile traversing " + m + ": " + msg) - m.dump() - global.abort("" + m) - } - def dumpMethodAndAbort(m: IMethod, b: BasicBlock): Nothing = - dumpMethodAndAbort(m, "found open block " + b + " " + b.flagsString) - - def checkValid(m: IMethod) { - // always slightly dicey to iterate over mutable structures - m foreachBlock { b => - if (!b.closed) { - // Something is leaving open/empty blocks around (see SI-4840) so - // let's not kill the deal unless it's nonempty. - if (b.isEmpty) { - devWarning(s"Found open but empty block while inlining $m: removing from block list.") - m.code removeBlock b - } - else dumpMethodAndAbort(m, b) - } - } - } - - object liveness extends Liveness { - val global: ICodes.this.global.type = ICodes.this.global - } - - object reachingDefinitions extends ReachingDefinitions { - val global: ICodes.this.global.type = ICodes.this.global - } - - lazy val AnyRefReference: TypeKind = REFERENCE(definitions.AnyRefClass) - lazy val BoxedUnitReference: TypeKind = REFERENCE(definitions.BoxedUnitClass) - lazy val NothingReference: TypeKind = REFERENCE(definitions.NothingClass) - lazy val NullReference: TypeKind = REFERENCE(definitions.NullClass) - lazy val ObjectReference: TypeKind = REFERENCE(definitions.ObjectClass) - lazy val StringReference: TypeKind = REFERENCE(definitions.StringClass) - - object icodeReader extends ICodeReader { - lazy val global: ICodes.this.global.type = ICodes.this.global - import global._ - def lookupMemberAtTyperPhaseIfPossible(sym: Symbol, name: Name): Symbol = - global.loaders.lookupMemberAtTyperPhaseIfPossible(sym, name) - lazy val symbolTable: global.type = global - lazy val loaders: global.loaders.type = global.loaders - - def classFileLookup: util.ClassFileLookup[AbstractFile] = global.classPath - } - - /** A phase which works on icode. */ - abstract class ICodePhase(prev: Phase) extends global.GlobalPhase(prev) { - override def erasedTypes = true - override def apply(unit: global.CompilationUnit): Unit = - unit.icode foreach apply - - def apply(cls: global.icodes.IClass): Unit - } -} - diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala deleted file mode 100644 index 54be9d18f1..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala +++ /dev/null @@ -1,201 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala -package tools.nsc -package backend -package icode - -import scala.collection.{ mutable, immutable } -import mutable.ListBuffer - -trait Linearizers { - self: ICodes => - - import global.debuglog - import opcodes._ - - abstract class Linearizer { - def linearize(c: IMethod): List[BasicBlock] - def linearizeAt(c: IMethod, start: BasicBlock): List[BasicBlock] - } - - /** - * A simple linearizer which predicts all branches to - * take the 'success' branch and tries to schedule those - * blocks immediately after the test. This is in sync with - * how 'while' statements are translated (if the test is - * 'true', the loop continues). - */ - class NormalLinearizer extends Linearizer with WorklistAlgorithm { - type Elem = BasicBlock - val worklist: WList = new mutable.Stack() - var blocks: List[BasicBlock] = Nil - - def linearize(m: IMethod): List[BasicBlock] = { - val b = m.startBlock - blocks = Nil - - run { - worklist pushAll (m.exh map (_.startBlock)) - worklist.push(b) - } - - blocks.reverse - } - - def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { - blocks = Nil - worklist.clear() - linearize(start) - } - - /** Linearize another subtree and append it to the existing blocks. */ - def linearize(startBlock: BasicBlock): List[BasicBlock] = { - //blocks = startBlock :: Nil; - run( { worklist.push(startBlock); } ) - blocks.reverse - } - - def processElement(b: BasicBlock) = - if (b.nonEmpty) { - add(b) - b.lastInstruction match { - case JUMP(whereto) => - add(whereto) - case CJUMP(success, failure, _, _) => - add(success) - add(failure) - case CZJUMP(success, failure, _, _) => - add(success) - add(failure) - case SWITCH(_, labels) => - add(labels) - case RETURN(_) => () - case THROW(clasz) => () - } - } - - def dequeue: Elem = worklist.pop() - - /** - * Prepend b to the list, if not already scheduled. - * TODO: use better test than linear search - */ - def add(b: BasicBlock) { - if (blocks.contains(b)) - () - else { - blocks = b :: blocks - worklist push b - } - } - - def add(bs: List[BasicBlock]): Unit = bs foreach add - } - - /** - * Linearize code using a depth first traversal. - */ - class DepthFirstLinerizer extends Linearizer { - var blocks: List[BasicBlock] = Nil - - def linearize(m: IMethod): List[BasicBlock] = { - blocks = Nil - - dfs(m.startBlock) - m.exh foreach (b => dfs(b.startBlock)) - - blocks.reverse - } - - def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { - blocks = Nil - dfs(start) - blocks.reverse - } - - def dfs(b: BasicBlock): Unit = - if (b.nonEmpty && add(b)) - b.successors foreach dfs - - /** - * Prepend b to the list, if not already scheduled. - * TODO: use better test than linear search - * @return Returns true if the block was added. - */ - def add(b: BasicBlock): Boolean = - !(blocks contains b) && { - blocks = b :: blocks - true - } - } - - /** - * Linearize code in reverse post order. In fact, it does - * a post order traversal, prepending visited nodes to the list. - * This way, it is constructed already in reverse post order. - */ - class ReversePostOrderLinearizer extends Linearizer { - var blocks: List[BasicBlock] = Nil - val visited = new mutable.HashSet[BasicBlock] - val added = new mutable.BitSet - - def linearize(m: IMethod): List[BasicBlock] = { - blocks = Nil - visited.clear() - added.clear() - - m.exh foreach (b => rpo(b.startBlock)) - rpo(m.startBlock) - - // if the start block has predecessors, it won't be the first one - // in the linearization, so we need to enforce it here - if (m.startBlock.predecessors eq Nil) - blocks - else - m.startBlock :: (blocks.filterNot(_ == m.startBlock)) - } - - def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { - blocks = Nil - visited.clear() - added.clear() - - rpo(start) - blocks - } - - def rpo(b: BasicBlock): Unit = - if (b.nonEmpty && !visited(b)) { - visited += b - b.successors foreach rpo - add(b) - } - - /** - * Prepend b to the list, if not already scheduled. - * @return Returns true if the block was added. - */ - def add(b: BasicBlock) = { - debuglog("Linearizer adding block " + b.label) - - if (!added(b.label)) { - added += b.label - blocks = b :: blocks - } - } - } - - /** A 'dump' of the blocks in this method, which does not - * require any well-formedness of the basic blocks (like - * the last instruction being a jump). - */ - class DumpLinearizer extends Linearizer { - def linearize(m: IMethod): List[BasicBlock] = m.blocks - def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = sys.error("not implemented") - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala deleted file mode 100644 index 64146585e5..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala +++ /dev/null @@ -1,296 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala -package tools.nsc -package backend -package icode - -import scala.collection.{ mutable, immutable } -import scala.reflect.internal.util.{ SourceFile, NoSourceFile } - -trait ReferenceEquality { - override def hashCode = System.identityHashCode(this) - override def equals(that: Any) = this eq that.asInstanceOf[AnyRef] -} - -trait Members { - self: ICodes => - - import global._ - - object NoCode extends Code(null, TermName("NoCode")) { - override def blocksList: List[BasicBlock] = Nil - } - - /** - * This class represents the intermediate code of a method or - * other multi-block piece of code, like exception handlers. - */ - class Code(method: IMethod, name: Name) { - def this(method: IMethod) = this(method, method.symbol.name) - /** The set of all blocks */ - val blocks = mutable.ListBuffer[BasicBlock]() - - /** The start block of the method */ - var startBlock: BasicBlock = NoBasicBlock - - private var currentLabel: Int = 0 - private var _touched = false - - def blocksList: List[BasicBlock] = blocks.toList - def instructions = blocksList flatMap (_.iterator) - def blockCount = blocks.size - def instructionCount = (blocks map (_.length)).sum - - def touched = _touched - def touched_=(b: Boolean): Unit = { - @annotation.tailrec def loop(xs: List[BasicBlock]) { - xs match { - case Nil => - case x :: xs => x.touched = true ; loop(xs) - } - } - if (b) loop(blocks.toList) - - _touched = b - } - - // Constructor code - startBlock = newBlock() - - def removeBlock(b: BasicBlock) { - if (settings.debug) { - // only do this sanity check when debug is turned on because it's moderately expensive - val referers = blocks filter (_.successors contains b) - assert(referers.isEmpty, s"Trying to removing block $b (with preds ${b.predecessors.mkString}) but it is still refered to from block(s) ${referers.mkString}") - } - - if (b == startBlock) { - assert(b.successors.length == 1, - s"Removing start block ${b} with ${b.successors.length} successors (${b.successors.mkString})." - ) - startBlock = b.successors.head - } - - blocks -= b - assert(!blocks.contains(b)) - method.exh filter (_ covers b) foreach (_.covered -= b) - touched = true - } - - /** This methods returns a string representation of the ICode */ - override def toString = "ICode '" + name.decoded + "'" - - /* Compute a unique new label */ - def nextLabel: Int = { - currentLabel += 1 - currentLabel - } - - /* Create a new block and append it to the list - */ - def newBlock(): BasicBlock = { - touched = true - val block = new BasicBlock(nextLabel, method) - blocks += block - block - } - } - - /** Common interface for IClass/IField/IMethod. */ - trait IMember extends Ordered[IMember] { - def symbol: Symbol - - def compare(other: IMember) = - if (symbol eq other.symbol) 0 - else if (symbol isLess other.symbol) -1 - else 1 - - override def equals(other: Any): Boolean = - other match { - case other: IMember => (this compare other) == 0 - case _ => false - } - - override def hashCode = symbol.## - } - - /** Represent a class in ICode */ - class IClass(val symbol: Symbol) extends IMember { - var fields: List[IField] = Nil - var methods: List[IMethod] = Nil - var cunit: CompilationUnit = _ - - def addField(f: IField): this.type = { - fields = f :: fields - this - } - - def addMethod(m: IMethod): this.type = { - methods = m :: methods - this - } - - def setCompilationUnit(unit: CompilationUnit): this.type = { - this.cunit = unit - this - } - - override def toString() = symbol.fullName - - def lookupMethod(s: Symbol) = methods find (_.symbol == s) - - /* returns this methods static ctor if it has one. */ - def lookupStaticCtor: Option[IMethod] = methods find (_.symbol.isStaticConstructor) - } - - /** Represent a field in ICode */ - class IField(val symbol: Symbol) extends IMember { } - - object NoIMethod extends IMethod(NoSymbol) { } - - /** - * Represents a method in ICode. Local variables contain - * both locals and parameters, similar to the way the JVM - * 'sees' them. - * - * Locals and parameters are added in reverse order, as they - * are kept in cons-lists. The 'builder' is responsible for - * reversing them and putting them back, when the generation is - * finished (GenICode does that). - */ - class IMethod(val symbol: Symbol) extends IMember { - var code: Code = NoCode - - def newBlock() = code.newBlock() - def startBlock = code.startBlock - def lastBlock = { assert(blocks.nonEmpty, symbol); blocks.last } - def blocks = code.blocksList - def linearizedBlocks(lin: Linearizer = self.linearizer): List[BasicBlock] = lin linearize this - - def foreachBlock[U](f: BasicBlock => U): Unit = blocks foreach f - - var native = false - - /** The list of exception handlers, ordered from innermost to outermost. */ - var exh: List[ExceptionHandler] = Nil - var sourceFile: SourceFile = NoSourceFile - var returnType: TypeKind = _ - var recursive: Boolean = false - var bytecodeHasEHs = false // set by ICodeReader only, used by Inliner to prevent inlining (SI-6188) - var bytecodeHasInvokeDynamic = false // set by ICodeReader only, used by Inliner to prevent inlining until we have proper invoke dynamic support - - /** local variables and method parameters */ - var locals: List[Local] = Nil - - /** method parameters */ - var params: List[Local] = Nil - - def hasCode = code ne NoCode - def setCode(code: Code): IMethod = { - this.code = code - this - } - - final def updateRecursive(called: Symbol): Unit = { - recursive ||= (called == symbol) - } - - def addLocal(l: Local): Local = findOrElse(locals)(_ == l) { locals ::= l ; l } - - def addParam(p: Local): Unit = - if (params contains p) () - else { - params ::= p - locals ::= p - } - - def addLocals(ls: List[Local]) = ls foreach addLocal - - def lookupLocal(n: Name): Option[Local] = locals find (_.sym.name == n) - def lookupLocal(sym: Symbol): Option[Local] = locals find (_.sym == sym) - - def addHandler(e: ExceptionHandler) = exh ::= e - - /** Is this method deferred ('abstract' in Java sense)? - */ - def isAbstractMethod = symbol.isDeferred || symbol.owner.isInterface || native - - def isStatic: Boolean = symbol.isStaticMember - - override def toString() = symbol.fullName - - import opcodes._ - - /** Merge together blocks that have a single successor which has a - * single predecessor. Exception handlers are taken into account (they - * might force to break a block of straight line code like that). - * - * This method should be most effective after heavy inlining. - */ - def normalize(): Unit = if (this.hasCode) { - val nextBlock: mutable.Map[BasicBlock, BasicBlock] = mutable.HashMap.empty - for (b <- code.blocks.toList - if b.successors.length == 1; - succ = b.successors.head - if succ ne b - if succ.predecessors.length == 1 - if succ.predecessors.head eq b - if !(exh.exists { (e: ExceptionHandler) => - (e.covers(succ) && !e.covers(b)) || (e.covers(b) && !e.covers(succ)) })) { - nextBlock(b) = succ - } - - var bb = code.startBlock - while (!nextBlock.isEmpty) { - if (nextBlock.isDefinedAt(bb)) { - bb.open() - var succ = bb - do { - succ = nextBlock(succ) - val lastInstr = bb.lastInstruction - /* Ticket SI-5672 - * Besides removing the control-flow instruction at the end of `bb` (usually a JUMP), we have to pop any values it pushes. - * Examples: - * `SWITCH` consisting of just the default case, or - * `CJUMP(targetBlock, targetBlock, _, _)` ie where success and failure targets coincide (this one consumes two stack values). - */ - val oldTKs = lastInstr.consumedTypes - assert(lastInstr.consumed == oldTKs.size, "Someone forgot to override consumedTypes() in " + lastInstr) - - bb.removeLastInstruction() - for(tk <- oldTKs.reverse) { bb.emit(DROP(tk), lastInstr.pos) } - succ.toList foreach { i => bb.emit(i, i.pos) } - code.removeBlock(succ) - exh foreach { e => e.covered = e.covered - succ } - - nextBlock -= bb - } while (nextBlock.isDefinedAt(succ)) - bb.close() - } else - bb = nextBlock.keysIterator.next() - } - checkValid(this) - } - - def dump() { - Console.println("dumping IMethod(" + symbol + ")") - newTextPrinter() printMethod this - } - } - - /** Represent local variables and parameters */ - class Local(val sym: Symbol, val kind: TypeKind, val arg: Boolean) { - var index: Int = -1 - - override def equals(other: Any): Boolean = other match { - case x: Local => sym == x.sym - case _ => false - } - override def hashCode = sym.hashCode - override def toString(): String = sym.toString - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala deleted file mode 100644 index 351a8e33d3..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ /dev/null @@ -1,767 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala -package tools.nsc -package backend -package icode - -import scala.reflect.internal.util.{Position,NoPosition} - -/* - A pattern match - - // locals - case THIS(clasz) => - case STORE_THIS(kind) => - case LOAD_LOCAL(local) => - case STORE_LOCAL(local) => - case SCOPE_ENTER(lv) => - case SCOPE_EXIT(lv) => - // stack - case LOAD_MODULE(module) => - case LOAD_EXCEPTION(clasz) => - case DROP(kind) => - case DUP(kind) => - // constants - case CONSTANT(const) => - // arithlogic - case CALL_PRIMITIVE(primitive) => - // casts - case IS_INSTANCE(tpe) => - case CHECK_CAST(tpe) => - // objs - case NEW(kind) => - case MONITOR_ENTER() => - case MONITOR_EXIT() => - case BOX(boxType) => - case UNBOX(tpe) => - // flds - case LOAD_FIELD(field, isStatic) => - case STORE_FIELD(field, isStatic) => - // mthds - case CALL_METHOD(method, style) => - // arrays - case LOAD_ARRAY_ITEM(kind) => - case STORE_ARRAY_ITEM(kind) => - case CREATE_ARRAY(elem, dims) => - // jumps - case SWITCH(tags, labels) => - case JUMP(whereto) => - case CJUMP(success, failure, cond, kind) => - case CZJUMP(success, failure, cond, kind) => - // ret - case RETURN(kind) => - case THROW(clasz) => -*/ - - -/** - * The ICode intermediate representation. It is a stack-based - * representation, very close to the JVM and .NET. It uses the - * erased types of Scala and references Symbols to refer named entities - * in the source files. - */ -trait Opcodes { self: ICodes => - import global.{Symbol, NoSymbol, Name, Constant} - - // categories of ICode instructions - final val localsCat = 1 - final val stackCat = 2 - final val constCat = 3 - final val arilogCat = 4 - final val castsCat = 5 - final val objsCat = 6 - final val fldsCat = 7 - final val mthdsCat = 8 - final val arraysCat = 9 - final val jumpsCat = 10 - final val retCat = 11 - - private lazy val ObjectReferenceList = ObjectReference :: Nil - - /** This class represents an instruction of the intermediate code. - * Each case subclass will represent a specific operation. - */ - abstract class Instruction extends Cloneable { - // Vlad: I used these for checking the quality of the implementation, and we should regularly run a build with them - // enabled. But for production these should definitely be disabled, unless we enjoy getting angry emails from Greg :) - //if (!this.isInstanceOf[opcodes.LOAD_EXCEPTION]) - // assert(consumed == consumedTypes.length) - //assert(produced == producedTypes.length) - - def category: Int = 0 // undefined - - /** This abstract method returns the number of used elements on the stack */ - def consumed : Int = 0 - - /** This abstract method returns the number of produced elements on the stack */ - def produced : Int = 0 - - /** This instruction consumes these types from the top of the stack, the first - * element in the list is the deepest element on the stack. - */ - def consumedTypes: List[TypeKind] = Nil - - /** This instruction produces these types on top of the stack. */ - // Vlad: I wonder why we keep producedTypes around -- it looks like an useless thing to have - def producedTypes: List[TypeKind] = Nil - - /** The corresponding position in the source file */ - private var _pos: Position = NoPosition - - def pos: Position = _pos - - def setPos(p: Position): this.type = { - _pos = p - this - } - - /** Clone this instruction. */ - override def clone(): Instruction = - super.clone.asInstanceOf[Instruction] - } - - object opcodes { - /** Loads "this" on top of the stack. - * Stack: ... - * ->: ...:ref - */ - case class THIS(clasz: Symbol) extends Instruction { - /** Returns a string representation of this constant */ - override def toString = "THIS(" + clasz.name + ")" - - override def consumed = 0 - override def produced = 1 - - override def producedTypes = - // we're not allowed to have REFERENCE(Array), but what about compiling the Array class? Well, we use object for it. - if (clasz != global.definitions.ArrayClass) - REFERENCE(clasz) :: Nil - else - ObjectReference :: Nil - - override def category = localsCat - } - - /** Loads a constant on the stack. - * Stack: ... - * ->: ...:constant - */ - case class CONSTANT(constant: Constant) extends Instruction { - override def toString = "CONSTANT(" + constant.escapedStringValue + ")" - override def consumed = 0 - override def produced = 1 - - override def producedTypes = toTypeKind(constant.tpe) :: Nil - - override def category = constCat - } - - /** Loads an element of an array. The array and the index should - * be on top of the stack. - * Stack: ...:array[a](Ref):index(Int) - * ->: ...:element(a) - */ - case class LOAD_ARRAY_ITEM(kind: TypeKind) extends Instruction { - override def consumed = 2 - override def produced = 1 - - override def consumedTypes = ARRAY(kind) :: INT :: Nil - override def producedTypes = kind :: Nil - - override def category = arraysCat - } - - /** Load a local variable on the stack. It can be a method argument. - * Stack: ... - * ->: ...:value - */ - case class LOAD_LOCAL(local: Local) extends Instruction { - override def consumed = 0 - override def produced = 1 - - override def producedTypes = local.kind :: Nil - - override def category = localsCat - } - - /** Load a field on the stack. The object to which it refers should be - * on the stack. - * Stack: ...:ref (assuming isStatic = false) - * ->: ...:value - */ - case class LOAD_FIELD(field: Symbol, isStatic: Boolean) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String = - "LOAD_FIELD " + (if (isStatic) field.fullName else field.toString()) - - override def consumed = if (isStatic) 0 else 1 - override def produced = 1 - - override def consumedTypes = if (isStatic) Nil else REFERENCE(field.owner) :: Nil - override def producedTypes = toTypeKind(field.tpe) :: Nil - - // more precise information about how to load this field - // see #4283 - var hostClass: Symbol = field.owner - def setHostClass(cls: Symbol): this.type = { hostClass = cls; this } - - override def category = fldsCat - } - - case class LOAD_MODULE(module: Symbol) extends Instruction { - assert(module != NoSymbol, "Invalid module symbol") - /** Returns a string representation of this instruction */ - override def toString(): String = "LOAD_MODULE " + module - - override def consumed = 0 - override def produced = 1 - - override def producedTypes = REFERENCE(module) :: Nil - - override def category = stackCat - } - - /** Store a value into an array at a specified index. - * Stack: ...:array[a](Ref):index(Int):value(a) - * ->: ... - */ - case class STORE_ARRAY_ITEM(kind: TypeKind) extends Instruction { - override def consumed = 3 - override def produced = 0 - - override def consumedTypes = ARRAY(kind) :: INT :: kind :: Nil - - override def category = arraysCat - } - - /** Store a value into a local variable. It can be an argument. - * Stack: ...:value - * ->: ... - */ - case class STORE_LOCAL(local: Local) extends Instruction { - override def consumed = 1 - override def produced = 0 - - override def consumedTypes = local.kind :: Nil - - override def category = localsCat - } - - /** Store a value into a field. - * Stack: ...:ref:value (assuming isStatic=false) - * ->: ... - */ - case class STORE_FIELD(field: Symbol, isStatic: Boolean) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String = - "STORE_FIELD "+field + (if (isStatic) " (static)" else " (dynamic)") - - override def consumed = if(isStatic) 1 else 2 - - override def produced = 0 - - override def consumedTypes = - if (isStatic) - toTypeKind(field.tpe) :: Nil - else - REFERENCE(field.owner) :: toTypeKind(field.tpe) :: Nil - - override def category = fldsCat - } - - /** Store a value into the 'this' pointer. - * Stack: ...:ref - * ->: ... - */ - case class STORE_THIS(kind: TypeKind) extends Instruction { - override def consumed = 1 - override def produced = 0 - override def consumedTypes = kind :: Nil - override def category = localsCat - } - - /** Call a primitive function. - * Stack: ...:arg1:arg2:...:argn - * ->: ...:result - */ - case class CALL_PRIMITIVE(primitive: Primitive) extends Instruction { - override def consumed = primitive match { - case Negation(_) => 1 - case Test(_,_, true) => 1 - case Test(_,_, false) => 2 - case Comparison(_,_) => 2 - case Arithmetic(NOT,_) => 1 - case Arithmetic(_,_) => 2 - case Logical(_,_) => 2 - case Shift(_,_) => 2 - case Conversion(_,_) => 1 - case ArrayLength(_) => 1 - case StringConcat(_) => 2 - case StartConcat => 0 - case EndConcat => 1 - } - override def produced = 1 - - override def consumedTypes = primitive match { - case Negation(kind) => kind :: Nil - case Test(_, kind, true) => kind :: Nil - case Test(_, kind, false) => kind :: kind :: Nil - case Comparison(_, kind) => kind :: kind :: Nil - case Arithmetic(NOT, kind) => kind :: Nil - case Arithmetic(_, kind) => kind :: kind :: Nil - case Logical(_, kind) => kind :: kind :: Nil - case Shift(_, kind) => kind :: INT :: Nil - case Conversion(from, _) => from :: Nil - case ArrayLength(kind) => ARRAY(kind) :: Nil - case StringConcat(kind) => ConcatClass :: kind :: Nil - case StartConcat => Nil - case EndConcat => ConcatClass :: Nil - } - - override def producedTypes = primitive match { - case Negation(kind) => kind :: Nil - case Test(_, _, true) => BOOL :: Nil - case Test(_, _, false) => BOOL :: Nil - case Comparison(_, _) => INT :: Nil - case Arithmetic(_, kind) => kind :: Nil - case Logical(_, kind) => kind :: Nil - case Shift(_, kind) => kind :: Nil - case Conversion(_, to) => to :: Nil - case ArrayLength(_) => INT :: Nil - case StringConcat(_) => ConcatClass :: Nil - case StartConcat => ConcatClass :: Nil - case EndConcat => REFERENCE(global.definitions.StringClass) :: Nil - } - - override def category = arilogCat - } - - /** This class represents a CALL_METHOD instruction - * STYLE: dynamic / static(StaticInstance) - * Stack: ...:ref:arg1:arg2:...:argn - * ->: ...:result - * - * STYLE: static(StaticClass) - * Stack: ...:arg1:arg2:...:argn - * ->: ...:result - * - */ - case class CALL_METHOD(method: Symbol, style: InvokeStyle) extends Instruction with ReferenceEquality { - def toShortString = - "CALL_METHOD " + method.name +" ("+style+")" - - /** Returns a string representation of this instruction */ - override def toString(): String = - "CALL_METHOD " + method.fullName +" ("+style+")" - - var hostClass: Symbol = method.owner - def setHostClass(cls: Symbol): this.type = { hostClass = cls; this } - - /** This is specifically for preserving the target native Array type long - * enough that clone() can generate the right call. - */ - var targetTypeKind: TypeKind = UNIT // the default should never be used, so UNIT should fail fast. - def setTargetTypeKind(tk: TypeKind) = targetTypeKind = tk - - private def params = method.info.paramTypes - private def consumesInstance = style match { - case Static(false) => 0 - case _ => 1 - } - - override def consumed = params.length + consumesInstance - override def consumedTypes = { - val args = params map toTypeKind - if (consumesInstance > 0) ObjectReference :: args - else args - } - - private val producedList = toTypeKind(method.info.resultType) match { - case UNIT => Nil - case _ if method.isConstructor => Nil - case kind => kind :: Nil - } - override def produced = producedList.size - override def producedTypes = producedList - - /** object identity is equality for CALL_METHODs. Needed for - * being able to store such instructions into maps, when more - * than one CALL_METHOD to the same method might exist. - */ - - override def category = mthdsCat - } - - /** - * A place holder entry that allows us to parse class files with invoke dynamic - * instructions. Because the compiler doesn't yet really understand the - * behavior of invokeDynamic, this op acts as a poison pill. Any attempt to analyze - * this instruction will cause a failure. The only optimization that - * should ever look at non-Scala generated icode is the inliner, and it - * has been modified to not examine any method with invokeDynamic - * instructions. So if this poison pill ever causes problems then - * there's been a serious misunderstanding - */ - // TODO do the real thing - case class INVOKE_DYNAMIC(poolEntry: Int) extends Instruction { - private def error = sys.error("INVOKE_DYNAMIC is not fully implemented and should not be analyzed") - override def consumed = error - override def produced = error - override def producedTypes = error - override def category = error - } - - case class BOX(boxType: TypeKind) extends Instruction { - assert(boxType.isValueType && (boxType ne UNIT)) // documentation - override def toString(): String = "BOX " + boxType - override def consumed = 1 - override def consumedTypes = boxType :: Nil - override def produced = 1 - override def producedTypes = BOXED(boxType) :: Nil - override def category = objsCat - } - - case class UNBOX(boxType: TypeKind) extends Instruction { - assert(boxType.isValueType && !boxType.isInstanceOf[BOXED] && (boxType ne UNIT)) // documentation - override def toString(): String = "UNBOX " + boxType - override def consumed = 1 - override def consumedTypes = ObjectReferenceList - override def produced = 1 - override def producedTypes = boxType :: Nil - override def category = objsCat - } - - /** Create a new instance of a class through the specified constructor - * Stack: ...:arg1:arg2:...:argn - * ->: ...:ref - */ - case class NEW(kind: REFERENCE) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String = "NEW "+ kind - - override def consumed = 0 - - override def produced = 1 - - override def producedTypes = kind :: Nil - - /** The corresponding constructor call. */ - var init: CALL_METHOD = _ - - override def category = objsCat - } - - - /** This class represents a CREATE_ARRAY instruction - * Stack: ...:size_1:size_2:..:size_n - * ->: ...:arrayref - */ - case class CREATE_ARRAY(elem: TypeKind, dims: Int) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="CREATE_ARRAY "+elem + " x " + dims - - override def consumed = dims - - override def consumedTypes = List.fill(dims)(INT) - override def produced = 1 - - override def producedTypes = ARRAY(elem) :: Nil - - override def category = arraysCat - } - - /** This class represents a IS_INSTANCE instruction - * Stack: ...:ref - * ->: ...:result(boolean) - */ - case class IS_INSTANCE(typ: TypeKind) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="IS_INSTANCE "+typ - - override def consumed = 1 - override def produced = 1 - override def consumedTypes = ObjectReferenceList - override def producedTypes = BOOL :: Nil - - override def category = castsCat - } - - /** This class represents a CHECK_CAST instruction - * Stack: ...:ref(oldtype) - * ->: ...:ref(typ <=: oldtype) - */ - case class CHECK_CAST(typ: TypeKind) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="CHECK_CAST "+typ - - override def consumed = 1 - override def produced = 1 - override def consumedTypes = ObjectReferenceList - override def producedTypes = typ :: Nil - - override def category = castsCat - } - - /** This class represents a SWITCH instruction - * Stack: ...:index(int) - * ->: ...: - * - * The tags array contains one entry per label, each entry consisting of - * an array of ints, any of which will trigger the jump to the corresponding label. - * labels should contain an extra label, which is the 'default' jump. - */ - case class SWITCH(tags: List[List[Int]], labels: List[BasicBlock]) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="SWITCH ..." - - override def consumed = 1 - override def produced = 0 - - override def consumedTypes = INT :: Nil - - def flatTagsCount: Int = { var acc = 0; var rest = tags; while(rest.nonEmpty) { acc += rest.head.length; rest = rest.tail }; acc } // a one-liner - - override def category = jumpsCat - } - - /** This class represents a JUMP instruction - * Stack: ... - * ->: ... - */ - case class JUMP(whereto: BasicBlock) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="JUMP "+whereto.label - - override def consumed = 0 - override def produced = 0 - - override def category = jumpsCat - } - - /** This class represents a CJUMP instruction - * It compares the two values on the stack with the 'cond' test operator - * Stack: ...:value1:value2 - * ->: ... - */ - case class CJUMP(successBlock: BasicBlock, - failureBlock: BasicBlock, - cond: TestOp, - kind: TypeKind) extends Instruction - { - - /** Returns a string representation of this instruction */ - override def toString(): String = ( - "CJUMP (" + kind + ")" + - cond + " ? "+successBlock.label+" : "+failureBlock.label - ) - - override def consumed = 2 - override def produced = 0 - - override def consumedTypes = kind :: kind :: Nil - - override def category = jumpsCat - } - - /** This class represents a CZJUMP instruction - * It compares the one value on the stack and zero with the 'cond' test operator - * Stack: ...:value: - * ->: ... - */ - case class CZJUMP(successBlock: BasicBlock, - failureBlock: BasicBlock, - cond: TestOp, - kind: TypeKind) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String = ( - "CZJUMP (" + kind + ")" + - cond + " ? "+successBlock.label+" : "+failureBlock.label - ) - - override def consumed = 1 - override def produced = 0 - - override def consumedTypes = kind :: Nil - override def category = jumpsCat - } - - - /** This class represents a RETURN instruction - * Stack: ... - * ->: ... - */ - case class RETURN(kind: TypeKind) extends Instruction { - override def consumed = if (kind == UNIT) 0 else 1 - override def produced = 0 - - override def consumedTypes = if (kind == UNIT) Nil else kind :: Nil - - override def category = retCat - } - - /** This class represents a THROW instruction - * Stack: ...:Throwable(Ref) - * ->: ...: - */ - case class THROW(clasz: Symbol) extends Instruction { - /** PP to ID: We discussed parameterizing LOAD_EXCEPTION but - * not THROW, which came about organically. It seems like the - * right thing, but can you confirm? - */ - override def toString = "THROW(" + clasz.name + ")" - - override def consumed = 1 - override def produced = 0 - - override def consumedTypes = toTypeKind(clasz.tpe) :: Nil - - override def category = retCat - } - - /** This class represents a DROP instruction - * Stack: ...:something - * ->: ... - */ - case class DROP (typ: TypeKind) extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="DROP "+typ - - override def consumed = 1 - override def produced = 0 - - override def consumedTypes = typ :: Nil - - override def category = stackCat - } - - /** This class represents a DUP instruction - * Stack: ...:something - * ->: ...:something:something - */ - case class DUP (typ: TypeKind) extends Instruction { - override def consumed = 1 - override def produced = 2 - override def consumedTypes = typ :: Nil - override def producedTypes = typ :: typ :: Nil - override def category = stackCat - } - - /** This class represents a MONITOR_ENTER instruction - * Stack: ...:object(ref) - * ->: ...: - */ - case class MONITOR_ENTER() extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="MONITOR_ENTER" - - override def consumed = 1 - override def produced = 0 - - override def consumedTypes = ObjectReference :: Nil - - override def category = objsCat - } - - /** This class represents a MONITOR_EXIT instruction - * Stack: ...:object(ref) - * ->: ...: - */ - case class MONITOR_EXIT() extends Instruction { - /** Returns a string representation of this instruction */ - override def toString(): String ="MONITOR_EXIT" - - override def consumed = 1 - - override def produced = 0 - - override def consumedTypes = ObjectReference :: Nil - - override def category = objsCat - } - - /** A local variable becomes visible at this point in code. - * Used only for generating precise local variable tables as - * debugging information. - */ - case class SCOPE_ENTER(lv: Local) extends Instruction { - override def toString(): String = "SCOPE_ENTER " + lv - override def consumed = 0 - override def produced = 0 - override def category = localsCat - } - - /** A local variable leaves its scope at this point in code. - * Used only for generating precise local variable tables as - * debugging information. - */ - case class SCOPE_EXIT(lv: Local) extends Instruction { - override def toString(): String = "SCOPE_EXIT " + lv - override def consumed = 0 - override def produced = 0 - override def category = localsCat - } - - /** Fake instruction. It designates the VM who pushes an exception - * on top of the /empty/ stack at the beginning of each exception handler. - * Note: Unlike other instructions, it consumes all elements on the stack! - * then pushes one exception instance. - */ - case class LOAD_EXCEPTION(clasz: Symbol) extends Instruction { - override def consumed = sys.error("LOAD_EXCEPTION does clean the whole stack, no idea how many things it consumes!") - override def produced = 1 - override def producedTypes = REFERENCE(clasz) :: Nil - override def category = stackCat - } - - /** This class represents a method invocation style. */ - sealed abstract class InvokeStyle { - /** Is this a dynamic method call? */ - def isDynamic: Boolean = false - - /** Is this a static method call? */ - def isStatic: Boolean = false - - def isSuper: Boolean = false - - /** Is this an instance method call? */ - def hasInstance: Boolean = true - - /** Returns a string representation of this style. */ - override def toString(): String - } - - /** Virtual calls. - * On JVM, translated to either `invokeinterface` or `invokevirtual`. - */ - case object Dynamic extends InvokeStyle { - override def isDynamic = true - override def toString(): String = "dynamic" - } - - /** - * Special invoke: - * Static(true) is used for calls to private members, ie `invokespecial` on JVM. - * Static(false) is used for calls to class-level instance-less static methods, ie `invokestatic` on JVM. - */ - case class Static(onInstance: Boolean) extends InvokeStyle { - override def isStatic = true - override def hasInstance = onInstance - override def toString(): String = { - if(onInstance) "static-instance" - else "static-class" - } - } - - /** Call through super[mix]. - * On JVM, translated to `invokespecial`. - */ - case class SuperCall(mix: Name) extends InvokeStyle { - override def isSuper = true - override def toString(): String = { "super(" + mix + ")" } - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/Primitives.scala b/src/compiler/scala/tools/nsc/backend/icode/Primitives.scala deleted file mode 100644 index dd930ba52f..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/Primitives.scala +++ /dev/null @@ -1,247 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala.tools.nsc -package backend -package icode - -import java.io.PrintWriter - -trait Primitives { self: ICodes => - - /** This class represents a primitive operation. */ - class Primitive { - } - - - // type : (type) => type - // range: type <- { BOOL, Ix, Ux, Rx } - // jvm : {i, l, f, d}neg - case class Negation(kind: TypeKind) extends Primitive - - // type : zero ? (type) => BOOL : (type,type) => BOOL - // range: type <- { BOOL, Ix, Ux, Rx, REF } - // jvm : if{eq, ne, lt, ge, le, gt}, if{null, nonnull} - // if_icmp{eq, ne, lt, ge, le, gt}, if_acmp{eq,ne} - case class Test(op: TestOp, kind: TypeKind, zero: Boolean) extends Primitive - - // type : (type,type) => I4 - // range: type <- { Ix, Ux, Rx } - // jvm : lcmp, {f, d}cmp{l, g} - case class Comparison(op: ComparisonOp, kind: TypeKind) extends Primitive - - // type : (type,type) => type - // range: type <- { Ix, Ux, Rx } - // jvm : {i, l, f, d}{add, sub, mul, div, rem} - case class Arithmetic(op: ArithmeticOp, kind: TypeKind) extends Primitive - - // type : (type,type) => type - // range: type <- { BOOL, Ix, Ux } - // jvm : {i, l}{and, or, xor} - case class Logical(op: LogicalOp, kind: TypeKind) extends Primitive - - // type : (type,I4) => type - // range: type <- { Ix, Ux } - // jvm : {i, l}{shl, ushl, shr} - case class Shift(op: ShiftOp, kind: TypeKind) extends Primitive - - // type : (src) => dst - // range: src,dst <- { Ix, Ux, Rx } - // jvm : i2{l, f, d}, l2{i, f, d}, f2{i, l, d}, d2{i, l, f}, i2{b, c, s} - case class Conversion(src: TypeKind, dst: TypeKind) extends Primitive - - // type : (Array[REF]) => I4 - // range: type <- { BOOL, Ix, Ux, Rx, REF } - // jvm : arraylength - case class ArrayLength(kind: TypeKind) extends Primitive - - // type : (buf,el) => buf - // range: lf,rg <- { BOOL, Ix, Ux, Rx, REF, STR } - // jvm : It should call the appropriate 'append' method on StringBuffer - case class StringConcat(el: TypeKind) extends Primitive - - /** Signals the beginning of a series of concatenations. - * On the JVM platform, it should create a new StringBuffer - */ - case object StartConcat extends Primitive - - /** - * type: (buf) => STR - * jvm : It should turn the StringBuffer into a String. - */ - case object EndConcat extends Primitive - - /** Pretty printer for primitives */ - class PrimitivePrinter(out: PrintWriter) { - def print(s: String): PrimitivePrinter = { - out.print(s) - this - } - } - - /** This class represents a comparison operation. */ - class ComparisonOp { - - /** Returns a string representation of this operation. */ - override def toString(): String = this match { - case CMPL => "CMPL" - case CMP => "CMP" - case CMPG => "CMPG" - case _ => throw new RuntimeException("ComparisonOp unknown case") - } - } - - /** A comparison operation with -1 default for NaNs */ - case object CMPL extends ComparisonOp - - /** A comparison operation with no default for NaNs */ - case object CMP extends ComparisonOp - - /** A comparison operation with +1 default for NaNs */ - case object CMPG extends ComparisonOp - - - /** This class represents a test operation. */ - sealed abstract class TestOp { - - /** Returns the negation of this operation. */ - def negate(): TestOp - - /** Returns a string representation of this operation. */ - override def toString(): String - - /** used only from GenASM */ - def opcodeIF(): Int - - /** used only from GenASM */ - def opcodeIFICMP(): Int - - } - - /** An equality test */ - case object EQ extends TestOp { - def negate() = NE - override def toString() = "EQ" - override def opcodeIF() = scala.tools.asm.Opcodes.IFEQ - override def opcodeIFICMP() = scala.tools.asm.Opcodes.IF_ICMPEQ - } - - /** A non-equality test */ - case object NE extends TestOp { - def negate() = EQ - override def toString() = "NE" - override def opcodeIF() = scala.tools.asm.Opcodes.IFNE - override def opcodeIFICMP() = scala.tools.asm.Opcodes.IF_ICMPNE - } - - /** A less-than test */ - case object LT extends TestOp { - def negate() = GE - override def toString() = "LT" - override def opcodeIF() = scala.tools.asm.Opcodes.IFLT - override def opcodeIFICMP() = scala.tools.asm.Opcodes.IF_ICMPLT - } - - /** A greater-than-or-equal test */ - case object GE extends TestOp { - def negate() = LT - override def toString() = "GE" - override def opcodeIF() = scala.tools.asm.Opcodes.IFGE - override def opcodeIFICMP() = scala.tools.asm.Opcodes.IF_ICMPGE - } - - /** A less-than-or-equal test */ - case object LE extends TestOp { - def negate() = GT - override def toString() = "LE" - override def opcodeIF() = scala.tools.asm.Opcodes.IFLE - override def opcodeIFICMP() = scala.tools.asm.Opcodes.IF_ICMPLE - } - - /** A greater-than test */ - case object GT extends TestOp { - def negate() = LE - override def toString() = "GT" - override def opcodeIF() = scala.tools.asm.Opcodes.IFGT - override def opcodeIFICMP() = scala.tools.asm.Opcodes.IF_ICMPGT - } - - /** This class represents an arithmetic operation. */ - class ArithmeticOp { - - /** Returns a string representation of this operation. */ - override def toString(): String = this match { - case ADD => "ADD" - case SUB => "SUB" - case MUL => "MUL" - case DIV => "DIV" - case REM => "REM" - case NOT => "NOT" - case _ => throw new RuntimeException("ArithmeticOp unknown case") - } - } - - /** An arithmetic addition operation */ - case object ADD extends ArithmeticOp - - /** An arithmetic subtraction operation */ - case object SUB extends ArithmeticOp - - /** An arithmetic multiplication operation */ - case object MUL extends ArithmeticOp - - /** An arithmetic division operation */ - case object DIV extends ArithmeticOp - - /** An arithmetic remainder operation */ - case object REM extends ArithmeticOp - - /** Bitwise negation. */ - case object NOT extends ArithmeticOp - - /** This class represents a shift operation. */ - class ShiftOp { - - /** Returns a string representation of this operation. */ - override def toString(): String = this match { - case LSL => "LSL" - case ASR => "ASR" - case LSR => "LSR" - case _ => throw new RuntimeException("ShiftOp unknown case") - } - } - - /** A logical shift to the left */ - case object LSL extends ShiftOp - - /** An arithmetic shift to the right */ - case object ASR extends ShiftOp - - /** A logical shift to the right */ - case object LSR extends ShiftOp - - /** This class represents a logical operation. */ - class LogicalOp { - - /** Returns a string representation of this operation. */ - override def toString(): String = this match { - case AND => "AND" - case OR => "OR" - case XOR => "XOR" - case _ => throw new RuntimeException("LogicalOp unknown case") - } - } - - /** A bitwise AND operation */ - case object AND extends LogicalOp - - /** A bitwise OR operation */ - case object OR extends LogicalOp - - /** A bitwise XOR operation */ - case object XOR extends LogicalOp -} - diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala deleted file mode 100644 index 1fe33f78e7..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala +++ /dev/null @@ -1,126 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -import java.io.PrintWriter - -trait Printers { self: ICodes => - import global._ - - class TextPrinter(writer: PrintWriter, lin: Linearizer) { - private var margin = 0 - private var out = writer - - final val TAB = 2 - - def setWriter(w: PrintWriter) { out = w } - - def indent() { margin += TAB } - def undent() { margin -= TAB } - - def print(s: String) { out.print(s) } - def print(o: Any) { print(o.toString()) } - - def println(s: String) { - print(s) - println() - } - - def println() { - out.println() - var i = 0 - while (i < margin) { - print(" ") - i += 1 - } - } - - def printList[A](l: List[A], sep: String): Unit = l match { - case Nil => - case x :: Nil => print(x) - case x :: xs => print(x); print(sep); printList(xs, sep) - } - - def printList[A](pr: A => Unit)(l: List[A], sep: String): Unit = l match { - case Nil => - case x :: Nil => pr(x) - case x :: xs => pr(x); print(sep); printList(pr)(xs, sep) - } - - def printClass(cls: IClass) { - print(cls.symbol.toString()); print(" extends ") - printList(cls.symbol.info.parents, ", ") - indent(); println(" {") - println("// fields:") - cls.fields.foreach(printField); println() - println("// methods") - cls.methods.foreach(printMethod) - undent(); println() - println("}") - } - - def printField(f: IField) { - print(f.symbol.keyString); print(" ") - print(f.symbol.nameString); print(": ") - println(f.symbol.info.toString()) - } - - def printMethod(m: IMethod) { - print("def "); print(m.symbol.name) - print("("); printList(printParam)(m.params, ", "); print(")") - print(": "); print(m.symbol.info.resultType) - - if (!m.isAbstractMethod) { - println(" {") - println("locals: " + m.locals.mkString("", ", ", "")) - println("startBlock: " + m.startBlock) - println("blocks: " + m.code.blocks.mkString("[", ",", "]")) - println() - lin.linearize(m) foreach printBlock - println("}") - - indent(); println("Exception handlers: ") - m.exh foreach printExceptionHandler - - undent(); println() - } else - println() - } - - def printParam(p: Local) { - print(p.sym.name); print(": "); print(p.sym.info) - print(" ("); print(p.kind); print(")") - } - - def printExceptionHandler(e: ExceptionHandler) { - indent() - println("catch (" + e.cls.simpleName + ") in " + e.covered.toSeq.sortBy(_.label) + " starting at: " + e.startBlock) - println("consisting of blocks: " + e.blocks) - undent() - println("with finalizer: " + e.finalizer) - // linearizer.linearize(e.startBlock) foreach printBlock; - } - - def printBlock(bb: BasicBlock) { - print(bb.label) - if (bb.loopHeader) print("[loop header]") - print(": ") - if (settings.debug) print("pred: " + bb.predecessors + " succs: " + bb.successors + " flags: " + bb.flagsString) - indent(); println() - bb.toList foreach printInstruction - undent(); println() - } - - def printInstruction(i: Instruction) { -// if (settings.Xdce.value) -// print(if (i.useful) " " else " * "); - if (i.pos.isDefined) print(i.pos.line.toString + "\t") else print("?\t") - println(i.toString()) - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/Repository.scala b/src/compiler/scala/tools/nsc/backend/icode/Repository.scala deleted file mode 100644 index 10d57df4a3..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/Repository.scala +++ /dev/null @@ -1,47 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala.tools.nsc -package backend -package icode - -import scala.collection._ - -/** - * @author Iulian Dragos - */ -trait Repository { - val global: Global - import global._ - import icodes._ - - val loaded: mutable.Map[Symbol, IClass] = perRunCaches.newMap() - - /** Is the given class available as icode? */ - def available(sym: Symbol) = classes.contains(sym) || loaded.contains(sym) - - /** The icode of the given class, if available */ - def icode(sym: Symbol): Option[IClass] = (classes get sym) orElse (loaded get sym) - - /** Load bytecode for given symbol. */ - def load(sym: Symbol): Boolean = { - try { - val (c1, c2) = icodeReader.readClass(sym) - - assert(c1.symbol == sym || c2.symbol == sym, "c1.symbol = %s, c2.symbol = %s, sym = %s".format(c1.symbol, c2.symbol, sym)) - loaded += (c1.symbol -> c1) - loaded += (c2.symbol -> c2) - - true - } catch { - case e: Throwable => // possible exceptions are MissingRequirementError, IOException and TypeError -> no better common supertype - log("Failed to load %s. [%s]".format(sym.fullName, e.getMessage)) - if (settings.debug) { e.printStackTrace } - - false - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala deleted file mode 100644 index a6d0d3b9fa..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala +++ /dev/null @@ -1,438 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -/* A type case - - case UNIT => - case BOOL => - case BYTE => - case SHORT => - case CHAR => - case INT => - case LONG => - case FLOAT => - case DOUBLE => - case REFERENCE(cls) => - case ARRAY(elem) => - -*/ - -trait TypeKinds { self: ICodes => - import global._ - import definitions.{ ArrayClass, AnyRefClass, ObjectClass, NullClass, NothingClass, arrayType } - - /** A map from scala primitive Types to ICode TypeKinds */ - lazy val primitiveTypeMap: Map[Symbol, TypeKind] = { - import definitions._ - Map( - UnitClass -> UNIT, - BooleanClass -> BOOL, - CharClass -> CHAR, - ByteClass -> BYTE, - ShortClass -> SHORT, - IntClass -> INT, - LongClass -> LONG, - FloatClass -> FLOAT, - DoubleClass -> DOUBLE - ) - } - /** Reverse map for toType */ - private lazy val reversePrimitiveMap: Map[TypeKind, Symbol] = - (primitiveTypeMap map (_.swap)).toMap - - /** This class represents a type kind. Type kinds - * represent the types that the VM know (or the ICode - * view of what VMs know). - */ - sealed abstract class TypeKind { - def maxType(other: TypeKind): TypeKind - - def toType: Type = reversePrimitiveMap get this map (_.tpe) getOrElse { - this match { - case REFERENCE(cls) => cls.tpe_* - case ARRAY(elem) => arrayType(elem.toType) - case _ => abort("Unknown type kind.") - } - } - - def isReferenceType = false - def isArrayType = false - def isValueType = false - def isBoxedType = false - final def isRefOrArrayType = isReferenceType || isArrayType - final def isNothingType = this == NothingReference - final def isNullType = this == NullReference - final def isInterfaceType = this match { - case REFERENCE(cls) if cls.isInterface || cls.isTrait => true - case _ => false - } - - /** On the JVM, - * BOOL, BYTE, CHAR, SHORT, and INT - * are like Ints for the purposes of calculating the lub. - */ - def isIntSizedType: Boolean = false - - /** On the JVM, similar to isIntSizedType except that BOOL isn't integral while LONG is. */ - def isIntegralType: Boolean = false - - /** On the JVM, FLOAT and DOUBLE. */ - def isRealType: Boolean = false - - final def isNumericType: Boolean = isIntegralType | isRealType - - /** Simple subtyping check */ - def <:<(other: TypeKind): Boolean - - /** - * this is directly assignable to other if no coercion or - * casting is needed to convert this to other. It's a distinct - * relationship from <:< because on the JVM, BOOL, BYTE, CHAR, - * SHORT need no coercion to INT even though JVM arrays - * are covariant, ARRAY[SHORT] is not a subtype of ARRAY[INT] - */ - final def isAssignabledTo(other: TypeKind): Boolean = other match { - case INT => this.isIntSizedType - case _ => this <:< other - } - - /** Is this type a category 2 type in JVM terms? (ie, is it LONG or DOUBLE?) */ - def isWideType: Boolean = false - - /** The number of dimensions for array types. */ - def dimensions: Int = 0 - - protected def uncomparable(thisKind: String, other: TypeKind): Nothing = - abort("Uncomparable type kinds: " + thisKind + " with " + other) - - protected def uncomparable(other: TypeKind): Nothing = - uncomparable(this.toString, other) - } - - sealed abstract class ValueTypeKind extends TypeKind { - override def isValueType = true - override def toString = { - this.getClass.getName stripSuffix "$" dropWhile (_ != '$') drop 1 - } - def <:<(other: TypeKind): Boolean = this eq other - } - - /** - * The least upper bound of two typekinds. They have to be either - * REFERENCE or ARRAY kinds. - * - * The lub is based on the lub of scala types. - */ - def lub(a: TypeKind, b: TypeKind): TypeKind = { - /* The compiler's lub calculation does not order classes before traits. - * This is apparently not wrong but it is inconvenient, and causes the - * icode checker to choke when things don't match up. My attempts to - * alter the calculation at the compiler level were failures, so in the - * interests of a working icode checker I'm making the adjustment here. - * - * Example where we'd like a different answer: - * - * abstract class Tom - * case object Bob extends Tom - * case object Harry extends Tom - * List(Bob, Harry) // compiler calculates "Product with Tom" rather than "Tom with Product" - * - * Here we make the adjustment by rewinding to a pre-erasure state and - * sifting through the parents for a class type. - */ - def lub0(tk1: TypeKind, tk2: TypeKind): Type = enteringUncurry { - val tp = global.lub(List(tk1.toType, tk2.toType)) - val (front, rest) = tp.parents span (_.typeSymbol.isTrait) - - if (front.isEmpty || rest.isEmpty || rest.head.typeSymbol == ObjectClass) tp - else rest.head - } - - def isIntLub = ( - (a == INT && b.isIntSizedType) || - (b == INT && a.isIntSizedType) - ) - - if (a == b) a - else if (a.isNothingType) b - else if (b.isNothingType) a - else if (a.isBoxedType || b.isBoxedType) AnyRefReference // we should do better - else if (isIntLub) INT - else if (a.isRefOrArrayType && b.isRefOrArrayType) { - if (a.isNullType) b - else if (b.isNullType) a - else toTypeKind(lub0(a, b)) - } - else throw new CheckerException("Incompatible types: " + a + " with " + b) - } - - /** The unit value */ - case object UNIT extends ValueTypeKind { - def maxType(other: TypeKind) = other match { - case UNIT | REFERENCE(NothingClass) => UNIT - case _ => uncomparable(other) - } - } - - /** A boolean value */ - case object BOOL extends ValueTypeKind { - override def isIntSizedType = true - def maxType(other: TypeKind) = other match { - case BOOL | REFERENCE(NothingClass) => BOOL - case _ => uncomparable(other) - } - } - - /** Note that the max of Char/Byte and Char/Short is Int, because - * neither strictly encloses the other due to unsignedness. - * See ticket #2087 for a consequence. - */ - - /** A 1-byte signed integer */ - case object BYTE extends ValueTypeKind { - override def isIntSizedType = true - override def isIntegralType = true - def maxType(other: TypeKind) = { - if (other == BYTE || other.isNothingType) BYTE - else if (other == CHAR) INT - else if (other.isNumericType) other - else uncomparable(other) - } - } - - /** A 2-byte signed integer */ - case object SHORT extends ValueTypeKind { - override def isIntSizedType = true - override def isIntegralType = true - override def maxType(other: TypeKind) = other match { - case BYTE | SHORT | REFERENCE(NothingClass) => SHORT - case CHAR => INT - case INT | LONG | FLOAT | DOUBLE => other - case _ => uncomparable(other) - } - } - - /** A 2-byte UNSIGNED integer */ - case object CHAR extends ValueTypeKind { - override def isIntSizedType = true - override def isIntegralType = true - override def maxType(other: TypeKind) = other match { - case CHAR | REFERENCE(NothingClass) => CHAR - case BYTE | SHORT => INT - case INT | LONG | FLOAT | DOUBLE => other - case _ => uncomparable(other) - } - } - - /** A 4-byte signed integer */ - case object INT extends ValueTypeKind { - override def isIntSizedType = true - override def isIntegralType = true - override def maxType(other: TypeKind) = other match { - case BYTE | SHORT | CHAR | INT | REFERENCE(NothingClass) => INT - case LONG | FLOAT | DOUBLE => other - case _ => uncomparable(other) - } - } - - /** An 8-byte signed integer */ - case object LONG extends ValueTypeKind { - override def isIntegralType = true - override def isWideType = true - override def maxType(other: TypeKind): TypeKind = - if (other.isIntegralType || other.isNothingType) LONG - else if (other.isRealType) DOUBLE - else uncomparable(other) - } - - /** A 4-byte floating point number */ - case object FLOAT extends ValueTypeKind { - override def isRealType = true - override def maxType(other: TypeKind): TypeKind = - if (other == DOUBLE) DOUBLE - else if (other.isNumericType || other.isNothingType) FLOAT - else uncomparable(other) - } - - /** An 8-byte floating point number */ - case object DOUBLE extends ValueTypeKind { - override def isRealType = true - override def isWideType = true - override def maxType(other: TypeKind): TypeKind = - if (other.isNumericType || other.isNothingType) DOUBLE - else uncomparable(other) - } - - /** A class type. */ - final case class REFERENCE(cls: Symbol) extends TypeKind { - override def toString = "REF(" + cls + ")" - assert(cls ne null, - "REFERENCE to null class symbol.") - assert(cls != ArrayClass, - "REFERENCE to Array is not allowed, should be ARRAY[..] instead") - assert(cls != NoSymbol, - "REFERENCE to NoSymbol not allowed!") - - /** - * 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) = other match { - case REFERENCE(_) | ARRAY(_) => AnyRefReference - case _ => uncomparable("REFERENCE", other) - } - - /** Checks subtyping relationship. */ - def <:<(other: TypeKind) = isNothingType || (other match { - case REFERENCE(cls2) => cls.tpe <:< cls2.tpe - case ARRAY(_) => cls == NullClass - case _ => false - }) - override def isReferenceType = true - } - - def ArrayN(elem: TypeKind, dims: Int): ARRAY = { - assert(dims > 0) - if (dims == 1) ARRAY(elem) - else ARRAY(ArrayN(elem, dims - 1)) - } - - final case class ARRAY(elem: TypeKind) extends TypeKind { - override def toString = "ARRAY[" + elem + "]" - override def isArrayType = true - override def dimensions = 1 + elem.dimensions - - /** The ultimate element type of this array. */ - def elementKind: TypeKind = elem match { - case a @ ARRAY(_) => a.elementKind - case k => k - } - - /** - * 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) = other match { - case ARRAY(elem2) if elem == elem2 => ARRAY(elem) - case ARRAY(_) | REFERENCE(_) => AnyRefReference - case _ => uncomparable("ARRAY", other) - } - - /** Array subtyping is covariant, as in Java. Necessary for checking - * code that interacts with Java. */ - def <:<(other: TypeKind) = other match { - case ARRAY(elem2) => elem <:< elem2 - case REFERENCE(AnyRefClass | ObjectClass) => true // TODO: platform dependent! - case _ => false - } - } - - /** A boxed value. */ - case class BOXED(kind: TypeKind) extends TypeKind { - override def isBoxedType = true - - override def maxType(other: TypeKind) = other match { - case BOXED(`kind`) => this - case REFERENCE(_) | ARRAY(_) | BOXED(_) => AnyRefReference - case _ => uncomparable("BOXED", other) - } - - /** Checks subtyping relationship. */ - def <:<(other: TypeKind) = other match { - case BOXED(`kind`) => true - case REFERENCE(AnyRefClass | ObjectClass) => true // TODO: platform dependent! - case _ => false - } - } - - /** - * 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" - def <:<(other: TypeKind): Boolean = this eq other - - /** - * 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) = other match { - case REFERENCE(_) => AnyRefReference - case _ => uncomparable(other) - } - } - - ////////////////// Conversions ////////////////////////////// - - /** Return the TypeKind of the given type - * - * Call to dealiasWiden fixes #3003 (follow type aliases). Otherwise, - * arrayOrClassType below would return ObjectReference. - */ - def toTypeKind(t: Type): TypeKind = t.dealiasWiden match { - case ThisType(ArrayClass) => ObjectReference - case ThisType(sym) => REFERENCE(sym) - case SingleType(_, sym) => primitiveOrRefType(sym) - case ConstantType(_) => toTypeKind(t.underlying) - case TypeRef(_, sym, args) => primitiveOrClassType(sym, args) - case ClassInfoType(_, _, ArrayClass) => abort("ClassInfoType to ArrayClass!") - case ClassInfoType(_, _, sym) => primitiveOrRefType(sym) - - // !!! Iulian says types which make no sense after erasure should not reach here, - // which includes the ExistentialType, AnnotatedType, RefinedType. I don't know - // if the first two cases exist because they do or as a defensive measure, but - // at the time I added it, RefinedTypes were indeed reaching here. - case ExistentialType(_, t) => toTypeKind(t) - case AnnotatedType(_, t) => toTypeKind(t) - case RefinedType(parents, _) => parents map toTypeKind reduceLeft lub - // For sure WildcardTypes shouldn't reach here either, but when - // debugging such situations this may come in handy. - // case WildcardType => REFERENCE(ObjectClass) - case norm => abort( - "Unknown type: %s, %s [%s, %s] TypeRef? %s".format( - t, norm, t.getClass, norm.getClass, t.isInstanceOf[TypeRef] - ) - ) - } - - /** Return the type kind of a class, possibly an array type. - */ - private def arrayOrClassType(sym: Symbol, targs: List[Type]) = sym match { - case ArrayClass => ARRAY(toTypeKind(targs.head)) - case _ if sym.isClass => newReference(sym) - case _ => - assert(sym.isType, sym) // it must be compiling Array[a] - ObjectReference - } - /** Interfaces have to be handled delicately to avoid introducing - * spurious errors, but if we treat them all as AnyRef we lose too - * much information. - */ - private def newReference(sym: Symbol): TypeKind = { - // Can't call .toInterface (at this phase) or we trip an assertion. - // See PackratParser#grow for a method which fails with an apparent mismatch - // between "object PackratParsers$class" and "trait PackratParsers" - if (sym.isImplClass) { - // pos/spec-List.scala is the sole failure if we don't check for NoSymbol - val traitSym = sym.owner.info.decl(tpnme.interfaceName(sym.name)) - if (traitSym != NoSymbol) - return REFERENCE(traitSym) - } - REFERENCE(sym) - } - - private def primitiveOrRefType(sym: Symbol) = - primitiveTypeMap.getOrElse(sym, newReference(sym)) - private def primitiveOrClassType(sym: Symbol, targs: List[Type]) = - primitiveTypeMap.getOrElse(sym, arrayOrClassType(sym, targs)) -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala deleted file mode 100644 index 57d51dad49..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/TypeStacks.scala +++ /dev/null @@ -1,82 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend -package icode - -/** This trait ... - * - * @author Iulian Dragos - * @version 1.0 - */ -trait TypeStacks { - self: ICodes => - - /* This class simulates the type of the operand - * stack of the ICode. - */ - type Rep = List[TypeKind] - - class TypeStack(var types: Rep) { - if (types.nonEmpty) - checkerDebug("Created " + this) - - def this() = this(Nil) - def this(that: TypeStack) = this(that.types) - - def length: Int = types.length - def isEmpty = length == 0 - def nonEmpty = length != 0 - - /** Push a type on the type stack. UNITs are ignored. */ - def push(t: TypeKind) = { - 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. - */ - def pop: TypeKind = { - val t = types.head - types = types.tail - t - } - - /** Return the topmost two values on the stack. It assumes the stack - * is large enough. Topmost element first. - */ - def pop2: (TypeKind, TypeKind) = (pop, pop) - - /** Return the topmost three values on the stack. It assumes the stack - * is large enough. Topmost element first. - */ - def pop3: (TypeKind, TypeKind, TypeKind) = (pop, pop, pop) - - /** Drop the first n elements of the stack. */ - def pop(n: Int): List[TypeKind] = { - val prefix = types.take(n) - types = types.drop(n) - prefix - } - - def apply(n: Int): TypeKind = types(n) - - /* This method returns a String representation of the stack */ - override def toString() = - if (types.isEmpty) "[]" - else types.mkString("[", " ", "]") - - override def hashCode() = types.hashCode() - override def equals(other: Any): Boolean = other match { - case x: TypeStack => x.types == types - case _ => false - } - } - -} 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 */ -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala deleted file mode 100644 index a378998f8f..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ /dev/null @@ -1,92 +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 generic framework for data flow analysis. - */ -trait DataFlowAnalysis[L <: SemiLattice] { - /** A type for program points. */ - type P <: ProgramPoint[P] - val lattice: L - - val worklist: mutable.Set[P] = new mutable.LinkedHashSet - val in: mutable.Map[P, lattice.Elem] = new mutable.HashMap - val out: mutable.Map[P, lattice.Elem] = new mutable.HashMap - val visited: mutable.HashSet[P] = new mutable.HashSet - - /** collect statistics? */ - var stat = true - - /** the number of times we iterated before reaching a fixpoint. */ - var iterations = 0 - - /* Implement this function to initialize the worklist. */ - def init(f: => Unit): Unit = { - iterations = 0 - in.clear(); out.clear(); worklist.clear(); visited.clear() - f - } - - def run(): Unit - - /** Implements forward dataflow analysis: the transfer function is - * applied when inputs to a Program point change, to obtain the new - * output value. - * - * @param f the transfer function. - */ - def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = try { - while (!worklist.isEmpty) { - if (stat) iterations += 1 - //Console.println("worklist in: " + worklist); - val point = worklist.iterator.next(); worklist -= point; visited += point - //Console.println("taking out point: " + point + " worklist out: " + worklist); - val output = f(point, in(point)) - - if ((lattice.bottom == out(point)) || output != out(point)) { - // Console.println("Output changed at " + point - // + " from: " + out(point) + " to: " + output - // + " for input: " + in(point) + " and they are different: " + (output != out(point))) - out(point) = output - val succs = point.successors - succs foreach { p => - val updated = lattice.lub(in(p) :: (p.predecessors map out.apply), p.exceptionHandlerStart) - if(updated != in(p)) { - in(p) = updated - if (!worklist(p)) { worklist += p; } - } - } - } - } - } catch { - case e: NoSuchElementException => - Console.println("in: " + in.mkString("", "\n", "")) - Console.println("out: " + out.mkString("", "\n", "")) - e.printStackTrace - sys.error("Could not find element " + e.getMessage) - } - - def backwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = - while (worklist.nonEmpty) { - if (stat) iterations += 1 - val point = worklist.head - worklist -= point - - out(point) = lattice.lub(point.successors map in.apply, exceptional = false) // TODO check for exception handlers - val input = f(point, out(point)) - - if ((lattice.bottom == in(point)) || input != in(point)) { - in(point) = input - worklist ++= point.predecessors - } - } - -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala deleted file mode 100644 index 939641c3eb..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala +++ /dev/null @@ -1,102 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 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]] = perRunCaches.newMap() - val kill: mutable.Map[BasicBlock, Set[Local]] = perRunCaches.newMap() - - def init(m: IMethod) { - this.method = m - gen.clear() - kill.clear() - - m foreachBlock { b => - val (g, k) = genAndKill(b) - gen += (b -> g) - kill += (b -> k) - } - - init { - m foreachBlock { b => - worklist += 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 _ => () - } - (genSet, killSet) - } - - override def run() { - backwardAnalysis(blockTransfer) - if (settings.debug) { - linearizer.linearize(method).foreach(b => if (b != method.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 = { - debuglog("- " + i + "\nout: " + out + "\n") - i match { - case LOAD_LOCAL(l) => out + l - case STORE_LOCAL(l) => out - l - case _ => out - } - } - override def toString() = - (method.blocks map (b => "\nlive-in(%s)=%s\nlive-out(%s)=%s".format(b, in(b), b, out(b)))).mkString - } /* Liveness analysis */ -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/LubException.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/LubException.scala deleted file mode 100644 index e91bf7a044..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/LubException.scala +++ /dev/null @@ -1,12 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala.tools.nsc -package backend.icode.analysis - -class LubException(a: Any, b: Any, msg: String) extends Exception { - override def toString() = "Lub error: " + msg + a + b -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ProgramPoint.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ProgramPoint.scala deleted file mode 100644 index 4e4026f526..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/ProgramPoint.scala +++ /dev/null @@ -1,18 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala.tools.nsc -package 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] - def exceptionHandlerStart: Boolean -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala deleted file mode 100644 index fecd48ed27..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala +++ /dev/null @@ -1,250 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - - -package scala.tools.nsc -package backend.icode -package analysis - -import scala.collection.{ mutable, immutable } -import immutable.ListSet - -/** Compute reaching definitions. We are only interested in reaching - * definitions for local variables, since values on the stack - * behave as-if in SSA form: the closest instruction which produces a value - * on the stack is a reaching definition. - */ -abstract class ReachingDefinitions { - val global: Global - import global._ - import icodes._ - - /** The lattice for reaching definitions. Elements are - * a triple (local variable, basic block, index of instruction of that basic block) - */ - object rdefLattice extends SemiLattice { - type Definition = (Local, BasicBlock, Int) - type Elem = IState[ListSet[Definition], Stack] - type StackPos = ListSet[(BasicBlock, Int)] - type Stack = List[StackPos] - - private def referenceEqualSet(name: String) = new ListSet[Definition] with ReferenceEquality { - override def toString = "<" + name + ">" - } - - val top: Elem = IState(referenceEqualSet("top"), Nil) - val bottom: Elem = IState(referenceEqualSet("bottom"), Nil) - - /** The least upper bound is set inclusion for locals, and pairwise set inclusion for stacks. */ - def lub2(exceptional: Boolean)(a: Elem, b: Elem): Elem = { - if (bottom == a) b - else if (bottom == b) a - else IState(a.vars ++ b.vars, - if (a.stack.isEmpty) b.stack - else if (b.stack.isEmpty) a.stack - else { - // !!! These stacks are with some frequency not of the same size. - // I can't reverse engineer the logic well enough to say whether this - // indicates a problem. Even if it doesn't indicate a problem, - // it'd be nice not to call zip with mismatched sequences because - // it makes it harder to spot the real problems. - val result = (a.stack, b.stack).zipped map (_ ++ _) - if (settings.debug && (a.stack.length != b.stack.length)) - devWarning(s"Mismatched stacks in ReachingDefinitions#lub2: ${a.stack}, ${b.stack}, returning $result") - result - } - ) - } - } - - class ReachingDefinitionsAnalysis extends DataFlowAnalysis[rdefLattice.type] { - type P = BasicBlock - val lattice = rdefLattice - import lattice.{ Definition, Stack, Elem, StackPos } - var method: IMethod = _ - - val gen = mutable.Map[BasicBlock, ListSet[Definition]]() - val kill = mutable.Map[BasicBlock, ListSet[Local]]() - val drops = mutable.Map[BasicBlock, Int]() - val outStack = mutable.Map[BasicBlock, Stack]() - - def init(m: IMethod) { - this.method = m - - gen.clear() - kill.clear() - drops.clear() - outStack.clear() - - m foreachBlock { b => - val (g, k) = genAndKill(b) - val (d, st) = dropsAndGen(b) - - gen += (b -> g) - kill += (b -> k) - drops += (b -> d) - outStack += (b -> st) - } - - init { - m foreachBlock { b => - worklist += b - in(b) = lattice.bottom - out(b) = lattice.bottom - } - m.exh foreach { e => - in(e.startBlock) = lattice.IState(new ListSet[Definition], List(new StackPos)) - } - } - } - - import opcodes._ - - def genAndKill(b: BasicBlock): (ListSet[Definition], ListSet[Local]) = { - var genSet = ListSet[Definition]() - var killSet = ListSet[Local]() - for ((STORE_LOCAL(local), idx) <- b.toList.zipWithIndex) { - killSet = killSet + local - genSet = updateReachingDefinition(b, idx, genSet) - } - (genSet, killSet) - } - - private def dropsAndGen(b: BasicBlock): (Int, Stack) = { - var depth, drops = 0 - var stackOut: Stack = Nil - - for ((instr, idx) <- b.toList.zipWithIndex) { - instr match { - case LOAD_EXCEPTION(_) => () - case _ if instr.consumed > depth => - drops += (instr.consumed - depth) - depth = 0 - stackOut = Nil - case _ => - stackOut = stackOut.drop(instr.consumed) - depth -= instr.consumed - } - var prod = instr.produced - depth += prod - while (prod > 0) { - stackOut ::= ListSet((b, idx)) - prod -= 1 - } - } -// Console.println("drops(" + b + ") = " + drops) -// Console.println("stackout(" + b + ") = " + stackOut) - (drops, stackOut) - } - - override def run() { - forwardAnalysis(blockTransfer) - if (settings.debug) { - linearizer.linearize(method).foreach(b => if (b != method.startBlock) - assert(lattice.bottom != in(b), - "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? " + in(b) - + ": bot: " + lattice.bottom - + "\nin(b) == bottom: " + (in(b) == lattice.bottom) - + "\nbottom == in(b): " + (lattice.bottom == in(b)))) - } - } - - import opcodes._ - import lattice.IState - def updateReachingDefinition(b: BasicBlock, idx: Int, rd: ListSet[Definition]): ListSet[Definition] = { - val STORE_LOCAL(local) = b(idx) - val tmp = local - (rd filter { case (l, _, _) => l != tmp }) + ((tmp, b, idx)) - } - - private def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { - var locals: ListSet[Definition] = (in.vars filter { case (l, _, _) => !kill(b)(l) }) ++ gen(b) - if (locals eq lattice.bottom.vars) locals = new ListSet[Definition] - IState(locals, outStack(b) ::: in.stack.drop(drops(b))) - } - - /** Return the reaching definitions corresponding to the point after idx. */ - def interpret(b: BasicBlock, idx: Int, in: lattice.Elem): Elem = { - var locals = in.vars - var stack = in.stack - val instr = b(idx) - - instr match { - case STORE_LOCAL(l1) => - locals = updateReachingDefinition(b, idx, locals) - stack = stack.drop(instr.consumed) - case LOAD_EXCEPTION(_) => - stack = Nil - case _ => - stack = stack.drop(instr.consumed) - } - - var prod = instr.produced - while (prod > 0) { - stack ::= ListSet((b, idx)) - prod -= 1 - } - - IState(locals, stack) - } - - /** Return the instructions that produced the 'm' elements on the stack, below given 'depth'. - * for instance, findefs(bb, idx, 1, 1) returns the instructions that might have produced the - * value found below the topmost element of the stack. - */ - def findDefs(bb: BasicBlock, idx: Int, m: Int, depth: Int): List[(BasicBlock, Int)] = if (idx > 0) { - assert(bb.closed, bb) - - val instrs = bb.getArray - var res: List[(BasicBlock, Int)] = Nil - var i = idx - var n = m - var d = depth - // "I look for who produced the 'n' elements below the 'd' topmost slots of the stack" - while (n > 0 && i > 0) { - i -= 1 - val prod = instrs(i).produced - if (prod > d) { - res = (bb, i) :: res - n = n - (prod - d) - instrs(i) match { - case LOAD_EXCEPTION(_) => () - case _ => d = instrs(i).consumed - } - } else { - d -= prod - d += instrs(i).consumed - } - } - - if (n > 0) { - val stack = this.in(bb).stack - assert(stack.length >= n, "entry stack is too small, expected: " + n + " found: " + stack) - stack.drop(d).take(n) foreach { defs => - res = defs.toList ::: res - } - } - res - } else { - val stack = this.in(bb).stack - assert(stack.length >= m, "entry stack is too small, expected: " + m + " found: " + stack) - stack.drop(depth).take(m) flatMap (_.toList) - } - - /** Return the definitions that produced the topmost 'm' elements on the stack, - * and that reach the instruction at index 'idx' in basic block 'bb'. - */ - def findDefs(bb: BasicBlock, idx: Int, m: Int): List[(BasicBlock, Int)] = - findDefs(bb, idx, m, 0) - - override def toString: String = { - if (method eq null) "<null>" - else method.code.blocks map { b => - " entry(%s) = %s\n".format(b, in(b)) + - " exit(%s) = %s\n".format(b, out(b)) - } mkString ("ReachingDefinitions {\n", "\n", "\n}") - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/SemiLattice.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/SemiLattice.scala deleted file mode 100644 index f718c705c2..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/SemiLattice.scala +++ /dev/null @@ -1,49 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala.tools.nsc -package backend.icode -package analysis - -/** A complete lattice. - */ -trait SemiLattice { - type Elem <: AnyRef - - /** Hold together local variable and stack state. The - * equals method uses reference equality for top and bottom, - * and structural equality for other values. - */ - final case class IState[V, S](vars: V, stack: S) { - override def hashCode = vars.hashCode + stack.hashCode - override def equals(other: Any): Boolean = other match { - case x: IState[_, _] => - if ((this eq bottom) || (this eq top) || (x eq bottom) || (x eq top)) this eq x - else stack == x.stack && vars == x.vars - case _ => - false - } - private def tstring(x: Any): String = x match { - case xs: TraversableOnce[_] => xs map tstring mkString " " - case _ => "" + x - } - override def toString = "IState(" + tstring(vars) + ", " + tstring(stack) + ")" - } - - /** Return the least upper bound of a and b. */ - def lub2(exceptional: Boolean)(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], exceptional: Boolean): Elem = - if (xs.isEmpty) bottom - else try xs reduceLeft lub2(exceptional) - catch { case e: LubException => Console.println("Lub on blocks: " + xs) ; throw e } -} diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala deleted file mode 100644 index 64c9901a3e..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ /dev/null @@ -1,725 +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} -import java.util.concurrent.TimeUnit - -/** A data-flow analysis on types, that works on `ICode`. - * - * @author Iulian Dragos - */ -abstract class TypeFlowAnalysis { - val global: Global - import global._ - import definitions.{ ObjectClass, NothingClass, AnyRefClass, StringClass, ThrowableClass } - - /** The lattice of ICode types. - */ - object typeLattice extends SemiLattice { - type Elem = icodes.TypeKind - - val top = icodes.REFERENCE(ObjectClass) - val bottom = icodes.REFERENCE(NothingClass) - - def lub2(exceptional: Boolean)(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 SemiLattice { - import icodes._ - type Elem = TypeStack - - val top = new TypeStack - val bottom = new TypeStack - val exceptionHandlerStack = new TypeStack(List(REFERENCE(AnyRefClass))) - - def lub2(exceptional: Boolean)(s1: TypeStack, s2: TypeStack) = { - if (s1 eq bottom) s2 - else if (s2 eq bottom) s1 - else if ((s1 eq exceptionHandlerStack) || (s2 eq exceptionHandlerStack)) sys.error("merging with exhan stack") - else { -// if (s1.length != s2.length) -// throw new CheckerException("Incompatible stacks: " + s1 + " and " + s2); - new TypeStack((s1.types, s2.types).zipped map icodes.lub) - } - } - } - - /** A map which returns the bottom type for unfound elements */ - class VarBinding extends mutable.HashMap[icodes.Local, icodes.TypeKind] { - override def default(l: icodes.Local) = 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 SemiLattice { - type Elem = IState[VarBinding, icodes.TypeStack] - - val top = new Elem(new VarBinding, typeStackLattice.top) - val bottom = new Elem(new VarBinding, typeStackLattice.bottom) - - def lub2(exceptional: Boolean)(a: Elem, b: Elem) = { - val IState(env1, _) = a - val IState(env2, _) = b - - val resultingLocals = new VarBinding - env1 foreach { case (k, v) => - resultingLocals += ((k, typeLattice.lub2(exceptional)(v, env2(k)))) - } - env2 collect { case (k, v) if resultingLocals(k) eq typeLattice.bottom => - resultingLocals += ((k, typeLattice.lub2(exceptional)(v, env1(k)))) - } - val stack = - if (exceptional) typeStackLattice.exceptionHandlerStack - else typeStackLattice.lub2(exceptional)(a.stack, b.stack) - - IState(resultingLocals, stack) - } - } - - val timer = new Timer - - class MethodTFA extends DataFlowAnalysis[typeFlowLattice.type] { - import icodes._ - import icodes.opcodes._ - - type P = BasicBlock - val lattice = typeFlowLattice - - val STRING = icodes.REFERENCE(StringClass) - var method: IMethod = _ - - /** Initialize the in/out maps for the analysis of the given method. */ - def init(m: icodes.IMethod) { - this.method = m - //typeFlowLattice.lubs = 0 - init { - worklist += m.startBlock - worklist ++= (m.exh map (_.startBlock)) - m foreachBlock { b => - in(b) = typeFlowLattice.bottom - out(b) = typeFlowLattice.bottom - } - - // start block has var bindings for each of its parameters - val entryBindings = new VarBinding ++= (m.params map (p => ((p, p.kind)))) - in(m.startBlock) = lattice.IState(entryBindings, typeStackLattice.bottom) - - m.exh foreach { e => - in(e.startBlock) = lattice.IState(in(e.startBlock).vars, typeStackLattice.exceptionHandlerStack) - } - } - } - - def this(m: icodes.IMethod) { - this() - init(m) - } - - def run() = { - timer.start() - // icodes.lubs0 = 0 - forwardAnalysis(blockTransfer) - timer.stop - if (settings.debug) { - linearizer.linearize(method).foreach(b => if (b != method.startBlock) - assert(visited.contains(b), - "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? .." + visited)) - } - // log("" + method.symbol.fullName + " [" + method.code.blocks.size + " blocks] " - // + "\n\t" + iterations + " iterations: " + t + " ms." - // + "\n\tlubs: " + typeFlowLattice.lubs + " out of which " + icodes.lubs0 + " typer lubs") - } - - def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { - var result = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) - var instrs = b.toList - while(!instrs.isEmpty) { - val i = instrs.head - result = mutatingInterpret(result, i) - instrs = instrs.tail - } - result - } - - /** 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)) - mutatingInterpret(out, i) - } - - def mutatingInterpret(out: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = { - val bindings = out.vars - val stack = out.stack - - if (settings.debug) { - // Console.println("[before] 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) => - stack.pop2 match { - case (idxKind, ARRAY(elem)) => - assert(idxKind == INT || idxKind == CHAR || idxKind == SHORT || idxKind == BYTE) - stack.push(elem) - case (_, _) => - 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 cm @ CALL_METHOD(_, _) => - stack pop cm.consumed - cm.producedTypes foreach (stack push _) - - 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 => stack.pop - case _: JUMP => () - case _: CJUMP => stack.pop2 - case _: CZJUMP => 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() | MONITOR_EXIT() => stack.pop - - case SCOPE_ENTER(_) | SCOPE_EXIT(_) => () - - case LOAD_EXCEPTION(clasz) => - stack.pop(stack.length) - stack.push(toTypeKind(clasz.tpe)) - - case _ => - dumpClassesAndAbort("Unknown instruction: " + i) - } - out - } // interpret - - 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 stack = out.stack - - out.stack.pop(consumed) - for (g <- gens) g match { - case Bind(l, t) => - out.vars += (l -> t.getKind(in)) - case Push(t) => - stack.push(t.getKind(in)) - } - out - } - } - } - - case class CallsiteInfo(bb: icodes.BasicBlock, receiver: Symbol, stackLength: Int, concreteMethod: Symbol) - - /** - - A full type-flow analysis on a method computes in- and out-flows for each basic block (that's what MethodTFA does). - - For the purposes of Inliner, doing so guarantees that an abstract typestack-slot is available by the time an inlining candidate (a CALL_METHOD instruction) is visited. - This subclass (MTFAGrowable) of MethodTFA also aims at performing such analysis on CALL_METHOD instructions, with some differences: - - (a) early screening is performed while the type-flow is being computed (in an override of `blockTransfer`) by testing a subset of the conditions that Inliner checks later. - The reasoning here is: if the early check fails at some iteration, there's no chance a follow-up iteration (with a yet more lub-ed typestack-slot) will succeed. - Failure is sufficient to remove that particular CALL_METHOD from the typeflow's `remainingCALLs`. - A forward note: in case inlining occurs at some basic block B, all blocks reachable from B get their CALL_METHOD instructions considered again as candidates - (because of the more precise types that -- perhaps -- can be computed). - - (b) in case the early check does not fail, no conclusive decision can be made, thus the CALL_METHOD stays `isOnwatchlist`. - - In other words, `remainingCALLs` tracks those callsites that still remain as candidates for inlining, so that Inliner can focus on those. - `remainingCALLs` also caches info about the typestack just before the callsite, so as to spare computing them again at inlining time. - - Besides caching, a further optimization involves skipping those basic blocks whose in-flow and out-flow isn't needed anyway (as explained next). - A basic block lacking a callsite in `remainingCALLs`, when visited by the standard algorithm, won't cause any inlining. - But as we know from the way type-flows are computed, computing the in- and out-flow for a basic block relies in general on those of other basic blocks. - In detail, we want to focus on that sub-graph of the CFG such that control flow may reach a remaining candidate callsite. - Those basic blocks not in that subgraph can be skipped altogether. That's why: - - `forwardAnalysis()` in `MTFAGrowable` now checks for inclusion of a basic block in `relevantBBs` - - same check is performed before adding a block to the worklist, and as part of choosing successors. - The bookkeeping supporting on-the-fly pruning of irrelevant blocks requires overriding most methods of the dataflow-analysis. - - The rest of the story takes place in Inliner, which does not visit all of the method's basic blocks but only on those represented in `remainingCALLs`. - - @author Miguel Garcia, http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/ - - */ - class MTFAGrowable extends MethodTFA { - - import icodes._ - - val remainingCALLs = mutable.Map.empty[opcodes.CALL_METHOD, CallsiteInfo] - - val preCandidates = mutable.Set.empty[BasicBlock] - - var callerLin: Traversable[BasicBlock] = null - - override def run { - - timer.start() - forwardAnalysis(blockTransfer) - timer.stop - - /* Now that `forwardAnalysis(blockTransfer)` has finished, all inlining candidates can be found in `remainingCALLs`, - whose keys are callsites and whose values are pieces of information about the typestack just before the callsite in question. - In order to keep `analyzeMethod()` simple, we collect in `preCandidates` those basic blocks containing at least one candidate. */ - preCandidates.clear() - for(rc <- remainingCALLs) { - preCandidates += rc._2.bb - } - - if (settings.debug) { - for(b <- callerLin; if (b != method.startBlock) && preCandidates(b)) { - assert(visited.contains(b), - "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? .." + visited) - } - } - - } - - var shrinkedWatchlist = false - - /* - This is the method where information cached elsewhere is put to use. References are given those other places that populate those caches. - - The goal is avoiding computing type-flows for blocks we don't need (ie blocks not tracked in `relevantBBs`). The method used to add to `relevantBBs` is `putOnRadar`. - - Moreover, it's often the case that the last CALL_METHOD of interest ("of interest" equates to "being tracked in `isOnWatchlist`) isn't the last instruction on the block. - There are cases where the typeflows computed past this `lastInstruction` are needed, and cases when they aren't. - The reasoning behind this decision is described in `populatePerimeter()`. All `blockTransfer()` needs to do (in order to know at which instruction it can stop) - is querying `isOnPerimeter`. - - Upon visiting a CALL_METHOD that's an inlining candidate, the relevant pieces of information about the pre-instruction typestack are collected for future use. - That is, unless the candidacy test fails. The reasoning here is: if such early check fails at some iteration, there's no chance a follow-up iteration - (with a yet more lub-ed typestack-slot) will succeed. In case of failure we can safely remove the CALL_METHOD from both `isOnWatchlist` and `remainingCALLs`. - - */ - override def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { - var result = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) - - val stopAt = if(isOnPerimeter(b)) lastInstruction(b) else null - var isPastLast = false - - var instrs = b.toList - while(!isPastLast && !instrs.isEmpty) { - val i = instrs.head - - if(isOnWatchlist(i)) { - val cm = i.asInstanceOf[opcodes.CALL_METHOD] - val msym = cm.method - val paramsLength = msym.info.paramTypes.size - val receiver = result.stack.types.drop(paramsLength).head match { - case REFERENCE(s) => s - case _ => NoSymbol // e.g. the scrutinee is BOX(s) or ARRAY - } - val concreteMethod = inliner.lookupImplFor(msym, receiver) - val isCandidate = { - ( inliner.isClosureClass(receiver) || concreteMethod.isEffectivelyFinalOrNotOverridden || receiver.isEffectivelyFinalOrNotOverridden ) && - !blackballed(concreteMethod) - } - if(isCandidate) { - remainingCALLs(cm) = CallsiteInfo(b, receiver, result.stack.length, concreteMethod) - } else { - remainingCALLs.remove(cm) - isOnWatchlist.remove(cm) - shrinkedWatchlist = true - } - } - - isPastLast = (i eq stopAt) - - if(!isPastLast) { - result = mutatingInterpret(result, i) - instrs = instrs.tail - } - } - - result - } // end of method blockTransfer - - val isOnWatchlist = mutable.Set.empty[Instruction] - - val warnIfInlineFails = mutable.Set.empty[opcodes.CALL_METHOD] // cache for a given IMethod (ie cleared on Inliner.analyzeMethod). - - /* Each time CallerCalleeInfo.isSafeToInline determines a concrete callee is unsafe to inline in the current caller, - the fact is recorded in this TFA instance for the purpose of avoiding devoting processing to that callsite next time. - The condition of "being unsafe to inline in the current caller" sticks across inlinings and TFA re-inits - because it depends on the instructions of the callee, which stay unchanged during the course of `analyzeInc(caller)` - (with the caveat of the side-effecting `makePublic` in `helperIsSafeToInline`).*/ - val knownUnsafe = mutable.Set.empty[Symbol] - val knownSafe = mutable.Set.empty[Symbol] - val knownNever = mutable.Set.empty[Symbol] // `knownNever` needs be cleared only at the very end of the inlining phase (unlike `knownUnsafe` and `knownSafe`) - final def blackballed(msym: Symbol): Boolean = { knownUnsafe(msym) || knownNever(msym) } - - val relevantBBs = mutable.Set.empty[BasicBlock] - - /* - * Rationale to prevent some methods from ever being inlined: - * - * (1) inlining getters and setters results in exposing a private field, - * which may itself prevent inlining of the caller (at best) or - * lead to situations like SI-5442 ("IllegalAccessError when mixing optimized and unoptimized bytecode") - * - * (2) only invocations having a receiver object are considered (ie no static-methods are ever inlined). - * This is taken care of by checking `isDynamic` (ie virtual method dispatch) and `Static(true)` (ie calls to private members) - */ - private def isPreCandidate(cm: opcodes.CALL_METHOD): Boolean = { - val msym = cm.method - val style = cm.style - - !blackballed(msym) && - !msym.isConstructor && - (!msym.isAccessor || inliner.isClosureClass(msym.owner)) && - (style.isDynamic || (style.hasInstance && style.isStatic)) - } - - override def init(m: icodes.IMethod) { - super.init(m) - remainingCALLs.clear() - knownUnsafe.clear() - knownSafe.clear() - // initially populate the watchlist with all callsites standing a chance of being inlined - isOnWatchlist.clear() - relevantBBs.clear() - warnIfInlineFails.clear() - /* TODO Do we want to perform inlining in non-finally exception handlers? - * Seems counterproductive (the larger the method the less likely it will be JITed. - * It's not that putting on radar only `linearizer linearizeAt (m, m.startBlock)` makes for much shorter inlining times (a minor speedup nonetheless) - * but the effect on method size could be explored. */ - putOnRadar(m.linearizedBlocks(linearizer)) - populatePerimeter() - // usually but not always true (counterexample in SI-6015) `(relevantBBs.isEmpty || relevantBBs.contains(m.startBlock))` - } - - def conclusives(b: BasicBlock): List[opcodes.CALL_METHOD] = { - knownBeforehand(b) filter { cm => inliner.isMonadicMethod(cm.method) || inliner.hasInline(cm.method) } - } - - def knownBeforehand(b: BasicBlock): List[opcodes.CALL_METHOD] = { - b.toList collect { case c : opcodes.CALL_METHOD => c } filter { cm => isPreCandidate(cm) && isReceiverKnown(cm) } - } - - private def isReceiverKnown(cm: opcodes.CALL_METHOD): Boolean = { - cm.method.isEffectivelyFinalOrNotOverridden && cm.method.owner.isEffectivelyFinalOrNotOverridden - } - - private def putOnRadar(blocks: Traversable[BasicBlock]) { - for(bb <- blocks) { - val calls = bb.toList collect { case cm : opcodes.CALL_METHOD => cm } - for(c <- calls; if(inliner.hasInline(c.method))) { - warnIfInlineFails += c - } - val preCands = calls filter isPreCandidate - isOnWatchlist ++= preCands - } - relevantBBs ++= blocks - } - - /* those BBs in the argument are also included in the result */ - private def transitivePreds(starters: Traversable[BasicBlock]): Set[BasicBlock] = { - val result = mutable.Set.empty[BasicBlock] - var toVisit: List[BasicBlock] = starters.toList.distinct - while(toVisit.nonEmpty) { - val h = toVisit.head - toVisit = toVisit.tail - result += h - for(p <- h.predecessors; if !result(p) && !toVisit.contains(p)) { toVisit = p :: toVisit } - } - result.toSet - } - - /* A basic block B is "on the perimeter" of the current control-flow subgraph if none of its successors belongs to that subgraph. - * In that case, for the purposes of inlining, we're interested in the typestack right before the last inline candidate in B, not in those afterwards. - * In particular we can do without computing the outflow at B. */ - private def populatePerimeter() { - isOnPerimeter.clear() - var done = true - do { - val (frontier, toPrune) = (relevantBBs filter hasNoRelevantSuccs) partition isWatching - isOnPerimeter ++= frontier - relevantBBs --= toPrune - done = toPrune.isEmpty - } while(!done) - - lastInstruction.clear() - for (b <- isOnPerimeter; lastIns = b.toList.reverse find isOnWatchlist) { - lastInstruction += (b -> lastIns.get.asInstanceOf[opcodes.CALL_METHOD]) - } - - // assertion: "no relevant block can have a predecessor that is on perimeter" - assert((for (b <- relevantBBs; if transitivePreds(b.predecessors) exists isOnPerimeter) yield b).isEmpty) - } - - private val isOnPerimeter = mutable.Set.empty[BasicBlock] - private val lastInstruction = mutable.Map.empty[BasicBlock, opcodes.CALL_METHOD] - - def hasNoRelevantSuccs(x: BasicBlock): Boolean = { !(x.successors exists relevantBBs) } - - def isWatching(x: BasicBlock): Boolean = (x.toList exists isOnWatchlist) - - - - - /** - - This method is invoked after one or more inlinings have been performed in basic blocks whose in-flow is non-bottom (this makes a difference later). - What we know about those inlinings is given by: - - - `staleOut`: These are the blocks where a callsite was inlined. - For each callsite, all instructions in that block before the callsite were left in the block, and the rest moved to an `afterBlock`. - The out-flow of these basic blocks is thus in general stale, that's why we'll add them to the TFA worklist. - - - `inlined` : These blocks were spliced into the method's CFG as part of inlining. Being new blocks, they haven't been visited yet by the typeflow analysis. - - - `staleIn` : These blocks are what `doInline()` calls `afterBlock`s, ie the new home for instructions that previously appeared - after a callsite in a `staleOut` block. - - Based on the above information, we have to bring up-to-date the caches that `forwardAnalysis` and `blockTransfer` use to skip blocks and instructions. - Those caches are `relevantBBs` and `isOnPerimeter` (for blocks) and `isOnWatchlist` and `lastInstruction` (for CALL_METHODs). - Please notice that all `inlined` and `staleIn` blocks are reachable from `staleOut` blocks. - - The update takes place in two steps: - - (1) `staleOut foreach { so => putOnRadar(linearizer linearizeAt (m, so)) }` - This results in initial populations for `relevantBBs` and `isOnWatchlist`. - Because of the way `isPreCandidate` reuses previous decision-outcomes that are still valid, - this already prunes some candidates standing no chance of being inlined. - - (2) `populatePerimeter()` - Based on the CFG-subgraph determined in (1) as reflected in `relevantBBs`, - this method detects some blocks whose typeflows aren't needed past a certain CALL_METHOD - (not needed because none of its successors is relevant for the purposes of inlining, see `hasNoRelevantSuccs`). - The blocks thus chosen are said to be "on the perimeter" of the CFG-subgraph. - For each of them, its `lastInstruction` (after which no more typeflows are needed) is found. - - */ - def reinit(m: icodes.IMethod, staleOut: List[BasicBlock], inlined: scala.collection.Set[BasicBlock], staleIn: scala.collection.Set[BasicBlock]) { - if (this.method == null || this.method.symbol != m.symbol) { - init(m) - return - } else if(staleOut.isEmpty && inlined.isEmpty && staleIn.isEmpty) { - // this promotes invoking reinit if in doubt, no performance degradation will ensue! - return - } - - worklist.clear() // calling reinit(f: => Unit) would also clear visited, thus forgetting about blocks visited before reinit. - - // asserts conveying an idea what CFG shapes arrive here: - // staleIn foreach (p => assert( !in.isDefinedAt(p), p)) - // staleIn foreach (p => assert(!out.isDefinedAt(p), p)) - // inlined foreach (p => assert( !in.isDefinedAt(p), p)) - // inlined foreach (p => assert(!out.isDefinedAt(p), p)) - // inlined foreach (p => assert(!p.successors.isEmpty || p.lastInstruction.isInstanceOf[icodes.opcodes.THROW], p)) - // staleOut foreach (p => assert( in.isDefinedAt(p), p)) - - // remainingCALLs.clear() - isOnWatchlist.clear() - relevantBBs.clear() - - // never rewrite in(m.startBlock) - staleOut foreach { b => - enqueue(b) - out(b) = typeFlowLattice.bottom - } - // nothing else is added to the worklist, bb's reachable via succs will be tfa'ed - blankOut(inlined) - blankOut(staleIn) - // no need to add startBlocks from m.exh - - staleOut foreach { so => putOnRadar(linearizer linearizeAt (m, so)) } - populatePerimeter() - - } // end of method reinit - - /* this is not a general purpose method to add to the worklist, - * because the assert is expected to hold only when called from MTFAGrowable.reinit() */ - private def enqueue(b: BasicBlock) { - assert(in(b) ne typeFlowLattice.bottom) - if(!worklist.contains(b)) { worklist += b } - } - - private def blankOut(blocks: scala.collection.Set[BasicBlock]) { - blocks foreach { b => - in(b) = typeFlowLattice.bottom - out(b) = typeFlowLattice.bottom - } - } - - /* - This is basically the plain-old forward-analysis part of a dataflow algorithm, - adapted to skip non-relevant blocks (as determined by `reinit()` via `populatePerimeter()`). - - The adaptations are: - - - only relevant blocks dequeued from the worklist move on to have the transfer function applied - - - `visited` now means the transfer function was applied to the block, - but please notice that this does not imply anymore its out-flow to be different from bottom, - because a block on the perimeter will have per-instruction typeflows computed only up to its `lastInstruction`. - In case you need to know whether a visted block `v` has been "fully visited", evaluate `out(v) ne typeflowLattice.bottom` - - - given that the transfer function may remove callsite-candidates from the watchlist (thus, they are not candidates anymore) - there's an opportunity to detect whether a previously relevant block has been left without candidates. - That's what `shrinkedWatchlist` detects. Provided the block was on the perimeter, we know we can skip it from now now, - and we can also constrain the CFG-subgraph by finding a new perimeter (thus the invocation to `populatePerimeter()`). - */ - override def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = { - while (!worklist.isEmpty && relevantBBs.nonEmpty) { - if (stat) iterations += 1 - val point = worklist.iterator.next(); worklist -= point - if(relevantBBs(point)) { - shrinkedWatchlist = false - val output = f(point, in(point)) - visited += point - if(isOnPerimeter(point)) { - if(shrinkedWatchlist && !isWatching(point)) { - relevantBBs -= point - populatePerimeter() - } - } else { - val propagate = ((lattice.bottom == out(point)) || output != out(point)) - if (propagate) { - out(point) = output - val succs = point.successors filter relevantBBs - succs foreach { p => - assert((p.predecessors filter isOnPerimeter).isEmpty) - val existing = in(p) - // TODO move the following assertion to typeFlowLattice.lub2 for wider applicability (ie MethodTFA in addition to MTFAGrowable). - assert(existing == lattice.bottom || - p.exceptionHandlerStart || - (output.stack.length == existing.stack.length), - "Trying to merge non-bottom type-stacks with different stack heights. For a possible cause see SI-6157.") - val updated = lattice.lub(List(output, existing), p.exceptionHandlerStart) - if(updated != in(p)) { - in(p) = updated - enqueue(p) - } - } - } - } - } - } - } - - } - - class Timer { - var millis = 0L - - private var lastStart = 0L - - def start() { - lastStart = System.nanoTime() - } - - /** 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 = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - lastStart) - millis += elapsed - elapsed - } - } -} |