diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2015-06-07 07:37:21 +0200 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2015-06-07 07:37:21 +0200 |
commit | 6d0a498bab3aaff4747434fbfb5e17c8b26d676d (patch) | |
tree | 4aec601c60ea9b12156b73cc1372a44c085e91a3 /src | |
parent | 0bc7fa67d130f75079df79814b33ef073254e27a (diff) | |
parent | b2a78b3ab536658f79e4396201c730a8408d3dd2 (diff) | |
download | scala-6d0a498bab3aaff4747434fbfb5e17c8b26d676d.tar.gz scala-6d0a498bab3aaff4747434fbfb5e17c8b26d676d.tar.bz2 scala-6d0a498bab3aaff4747434fbfb5e17c8b26d676d.zip |
Merge pull request #4519 from lrytz/opt/nullness-2.11
Nullness Analysis for GenBCode
Diffstat (limited to 'src')
8 files changed, 1113 insertions, 22 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala new file mode 100644 index 0000000000..7bbe1e2a49 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala @@ -0,0 +1,251 @@ +package scala.tools.nsc +package backend.jvm +package analysis + +import scala.annotation.switch +import scala.collection.{mutable, immutable} +import scala.tools.asm.Opcodes +import scala.tools.asm.tree._ +import scala.tools.asm.tree.analysis.{Analyzer, Value, Frame, Interpreter} +import opt.BytecodeUtils._ + +object AliasingFrame { + private var _idCounter: Long = 0l + private def nextId = { _idCounter += 1; _idCounter } +} + +class AliasingFrame[V <: Value](nLocals: Int, nStack: Int) extends Frame[V](nLocals, nStack) { + import Opcodes._ + + // Auxiliary constructor required for implementing `AliasingAnalyzer.newFrame` + def this(src: Frame[_ <: V]) { + this(src.getLocals, src.getMaxStackSize) + init(src) + } + + /** + * For each slot (entry in the `values` array of the frame), an id that uniquely represents + * the object stored in it. If two values have the same id, they are aliases of the same + * object. + */ + private val aliasIds: Array[Long] = Array.fill(nLocals + nStack)(AliasingFrame.nextId) + + /** + * The object alias id of for a value index. + */ + def aliasId(entry: Int) = aliasIds(entry) + + /** + * Returns the indices of the values array which are aliases of the object `id`. + */ + def valuesWithAliasId(id: Long): Set[Int] = immutable.BitSet.empty ++ aliasIds.indices.iterator.filter(i => aliasId(i) == id) + + /** + * The set of aliased values for a given entry in the `values` array. + */ + def aliasesOf(entry: Int): Set[Int] = valuesWithAliasId(aliasIds(entry)) + + /** + * Define a new alias. For example, given + * var a = this // this, a have the same aliasId + * then an assignment + * b = a + * will set the same the aliasId for `b`. + */ + private def newAlias(assignee: Int, source: Int): Unit = { + aliasIds(assignee) = aliasIds(source) + } + + /** + * An assignment + * a = someUnknownValue() + * sets a fresh alias id for `a`. + * A stack value is also removed from its alias set when being consumed. + */ + private def removeAlias(assignee: Int): Unit = { + aliasIds(assignee) = AliasingFrame.nextId + } + + override def execute(insn: AbstractInsnNode, interpreter: Interpreter[V]): Unit = { + // Make the extendsion methods easier to use (otherwise we have to repeat `this`.stackTop) + def stackTop: Int = this.stackTop + def peekStack(n: Int): V = this.peekStack(n) + + // the val pattern `val (p, c) = f` still allocates a tuple (https://github.com/scala-opt/scala/issues/28) + val prodCons = InstructionStackEffect(insn, this) // needs to be called before super.execute, see its doc + val consumed = prodCons._1 + val produced = prodCons._2 + + super.execute(insn, interpreter) + + (insn.getOpcode: @switch) match { + case ALOAD => + newAlias(assignee = stackTop, source = insn.asInstanceOf[VarInsnNode].`var`) + + case DUP => + val top = stackTop + newAlias(assignee = top, source = top - 1) + + case DUP_X1 => + val top = stackTop + newAlias(assignee = top, source = top - 1) + newAlias(assignee = top - 1, source = top - 2) + newAlias(assignee = top - 2, source = top) + + case DUP_X2 => + // Check if the second element on the stack is size 2 + // https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.dup_x2 + val isSize2 = peekStack(1).getSize == 2 + val top = stackTop + newAlias(assignee = top, source = top - 1) + newAlias(assignee = top - 1, source = top - 2) + if (isSize2) { + // Size 2 values on the stack only take one slot in the `values` array + newAlias(assignee = top - 2, source = top) + } else { + newAlias(assignee = top - 2, source = top - 3) + newAlias(assignee = top - 3, source = top) + } + + case DUP2 => + val isSize2 = peekStack(0).getSize == 2 + val top = stackTop + if (isSize2) { + newAlias(assignee = top, source = top - 1) + } else { + newAlias(assignee = top - 1, source = top - 3) + newAlias(assignee = top, source = top - 2) + } + + case DUP2_X1 => + val isSize2 = peekStack(0).getSize == 2 + val top = stackTop + if (isSize2) { + newAlias(assignee = top, source = top - 1) + newAlias(assignee = top - 1, source = top - 2) + newAlias(assignee = top - 2, source = top) + } else { + newAlias(assignee = top, source = top - 2) + newAlias(assignee = top - 1, source = top - 3) + newAlias(assignee = top - 2, source = top - 4) + newAlias(assignee = top - 4, source = top) + newAlias(assignee = top - 5, source = top - 1) + } + + case DUP2_X2 => + val top = stackTop + // https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.dup2_x2 + val v1isSize2 = peekStack(0).getSize == 2 + if (v1isSize2) { + newAlias(assignee = top, source = top - 1) + newAlias(assignee = top - 1, source = top - 2) + val v2isSize2 = peekStack(1).getSize == 2 + if (v2isSize2) { + // Form 4 + newAlias(assignee = top - 2, source = top) + } else { + // Form 2 + newAlias(assignee = top - 2, source = top - 3) + newAlias(assignee = top - 3, source = top) + } + } else { + newAlias(assignee = top, source = top - 2) + newAlias(assignee = top - 1, source = top - 3) + newAlias(assignee = top - 2, source = top - 4) + val v3isSize2 = peekStack(2).getSize == 2 + if (v3isSize2) { + // Form 3 + newAlias(assignee = top - 3, source = top) + newAlias(assignee = top - 4, source = top - 1) + } else { + // Form 1 + newAlias(assignee = top - 3, source = top - 5) + newAlias(assignee = top - 4, source = top) + newAlias(assignee = top - 5, source = top - 1) + } + } + + case SWAP => + val top = stackTop + val idTop = aliasIds(top) + aliasIds(top) = aliasIds(top - 1) + aliasIds(top - 1) = idTop + + case opcode => + if (opcode == ASTORE) { + // Not a separate case because we need to remove the consumed stack value from alias sets after. + val stackTopBefore = stackTop - produced + consumed + val local = insn.asInstanceOf[VarInsnNode].`var` + newAlias(assignee = local, source = stackTopBefore) + // if the value written is size 2, it overwrites the subsequent slot, which is then no + // longer an alias of anything. see the corresponding case in `Frame.execute`. + if (getLocal(local).getSize == 2) + removeAlias(local + 1) + + // if the value at the preceding index is size 2, it is no longer valid, so we remove its + // aliasing. see corresponding case in `Frame.execute` + if (local > 0) { + val precedingValue = getLocal(local - 1) + if (precedingValue != null && precedingValue.getSize == 2) + removeAlias(local - 1) + } + } + + // Remove consumed stack values from aliasing sets. + // Example: iadd + // - before: local1, local2, stack1, consumed1, consumed2 + // - after: local1, local2, stack1, produced1 // stackTop = 3 + val firstConsumed = stackTop - produced + 1 // firstConsumed = 3 + for (i <- 0 until consumed) + removeAlias(firstConsumed + i) // remove aliases for 3 and 4 + + // We don't need to set the aliases ids for the produced values: the aliasIds array already + // contains fresh ids for non-used stack values (ensured by removeAlias). + } + } + + /** + * Merge the AliasingFrame `other` into this AliasingFrame. + * + * Aliases that are common in both frames are kept. Example: + * + * var x, y = null + * if (...) { + * x = a + * y = a // (x, y, a) are aliases + * } else { + * x = a + * y = b // (x, a) and (y, b) + * } + * [...] // (x, a) + */ + override def merge(other: Frame[_ <: V], interpreter: Interpreter[V]): Boolean = { + val valuesChanged = super.merge(other, interpreter) + var aliasesChanged = false + val aliasingOther = other.asInstanceOf[AliasingFrame[_]] + for (i <- aliasIds.indices) { + val thisAliases = aliasesOf(i) + val thisNotOther = thisAliases diff (thisAliases intersect aliasingOther.aliasesOf(i)) + if (thisNotOther.nonEmpty) { + aliasesChanged = true + thisNotOther foreach removeAlias + } + } + valuesChanged || aliasesChanged + } + + override def init(src: Frame[_ <: V]): Frame[V] = { + super.init(src) + compat.Platform.arraycopy(src.asInstanceOf[AliasingFrame[_]].aliasIds, 0, aliasIds, 0, aliasIds.length) + this + } +} + +/** + * An analyzer that uses AliasingFrames instead of bare Frames. This can be used when an analysis + * needs to track aliases, but doesn't require a more specific Frame subclass. + */ +class AliasingAnalyzer[V <: Value](interpreter: Interpreter[V]) extends Analyzer[V](interpreter) { + override def newFrame(nLocals: Int, nStack: Int): AliasingFrame[V] = new AliasingFrame(nLocals, nStack) + override def newFrame(src: Frame[_ <: V]): AliasingFrame[V] = new AliasingFrame(src) +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala new file mode 100644 index 0000000000..98e93c125b --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala @@ -0,0 +1,265 @@ +package scala.tools.nsc +package backend.jvm +package analysis + +import scala.annotation.switch +import scala.tools.asm.Opcodes._ +import scala.tools.asm.Type +import scala.tools.asm.tree.{MultiANewArrayInsnNode, InvokeDynamicInsnNode, MethodInsnNode, AbstractInsnNode} +import scala.tools.asm.tree.analysis.{Frame, Value} +import opt.BytecodeUtils._ +import collection.immutable + +object InstructionStackEffect { + private var cache: immutable.IntMap[(Int, Int)] = immutable.IntMap.empty + private def t(x: Int, y: Int): (Int, Int) = { + // x can go up to 255 (number of parameters of a method, dimensions in multianewarray) we cache + // x up to 10, which covers most cases and limits the cache. y doesn't go above 6 (see cases). + if (x > 10 || y > 6) (x, y) + else { + val key = (x << 8) + y // this would work for any x < 256 + if (cache contains key) { + cache(key) + } else { + val r = (x, y) + cache += key -> r + r + } + } + } + + /** + * Returns a pair with the number of stack values consumed and produced by `insn`. + * This method requires the `frame` to be in the state **before** executing / interpreting + * the `insn`. + */ + def apply[V <: Value](insn: AbstractInsnNode, frame: Frame[V]): (Int, Int) = { + def peekStack(n: Int): V = frame.peekStack(n) + + (insn.getOpcode: @switch) match { + // The order of opcodes is the same as in Frame.execute. + case NOP => t(0, 0) + + case ACONST_NULL | + ICONST_M1 | + ICONST_0 | + ICONST_1 | + ICONST_2 | + ICONST_3 | + ICONST_4 | + ICONST_5 | + LCONST_0 | + LCONST_1 | + FCONST_0 | + FCONST_1 | + FCONST_2 | + DCONST_0 | + DCONST_1 | + BIPUSH | + SIPUSH | + LDC | + ILOAD | + LLOAD | + FLOAD | + DLOAD | + ALOAD => t(0, 1) + + case IALOAD | + LALOAD | + FALOAD | + DALOAD | + AALOAD | + BALOAD | + CALOAD | + SALOAD => t(2, 1) + + case ISTORE | + LSTORE | + FSTORE | + DSTORE | + ASTORE => t(1, 0) + + case IASTORE | + LASTORE | + FASTORE | + DASTORE | + AASTORE | + BASTORE | + CASTORE | + SASTORE => t(3, 0) + + case POP => t(1, 0) + + case POP2 => + val isSize2 = peekStack(0).getSize == 2 + if (isSize2) t(1, 0) else t(2, 0) + + case DUP => t(0, 1) + + case DUP_X1 => t(2, 3) + + case DUP_X2 => + val isSize2 = peekStack(1).getSize == 2 + if (isSize2) t(2, 3) else t(3, 4) + + case DUP2 => + val isSize2 = peekStack(0).getSize == 2 + if (isSize2) t(0, 1) else t(0, 2) + + case DUP2_X1 => + val isSize2 = peekStack(0).getSize == 2 + if (isSize2) t(2, 3) else t(3, 4) + + case DUP2_X2 => + val v1isSize2 = peekStack(0).getSize == 2 + if (v1isSize2) { + val v2isSize2 = peekStack(1).getSize == 2 + if (v2isSize2) t(2, 3) else t(3, 4) + } else { + val v3isSize2 = peekStack(2).getSize == 2 + if (v3isSize2) t(3, 5) else t(4, 6) + } + + case SWAP => t(2, 2) + + case IADD | + LADD | + FADD | + DADD | + ISUB | + LSUB | + FSUB | + DSUB | + IMUL | + LMUL | + FMUL | + DMUL | + IDIV | + LDIV | + FDIV | + DDIV | + IREM | + LREM | + FREM | + DREM => t(2, 1) + + case INEG | + LNEG | + FNEG | + DNEG => t(1, 1) + + case ISHL | + LSHL | + ISHR | + LSHR | + IUSHR | + LUSHR | + IAND | + LAND | + IOR | + LOR | + IXOR | + LXOR => t(2, 1) + + case IINC => t(0, 0) + + case I2L | + I2F | + I2D | + L2I | + L2F | + L2D | + F2I | + F2L | + F2D | + D2I | + D2L | + D2F | + I2B | + I2C | + I2S => t(1, 1) + + case LCMP | + FCMPL | + FCMPG | + DCMPL | + DCMPG => t(2, 1) + + case IFEQ | + IFNE | + IFLT | + IFGE | + IFGT | + IFLE => t(1, 0) + + case IF_ICMPEQ | + IF_ICMPNE | + IF_ICMPLT | + IF_ICMPGE | + IF_ICMPGT | + IF_ICMPLE | + IF_ACMPEQ | + IF_ACMPNE => t(2, 0) + + case GOTO => t(0, 0) + + case JSR => t(0, 1) + + case RET => t(0, 0) + + case TABLESWITCH | + LOOKUPSWITCH => t(1, 0) + + case IRETURN | + LRETURN | + FRETURN | + DRETURN | + ARETURN => t(1, 0) // Frame.execute consumes one stack value + + case RETURN => t(0, 0) // Frame.execute does not change the stack + + case GETSTATIC => t(0, 1) + + case PUTSTATIC => t(1, 0) + + case GETFIELD => t(1, 1) + + case PUTFIELD => t(2, 0) + + case INVOKEVIRTUAL | + INVOKESPECIAL | + INVOKESTATIC | + INVOKEINTERFACE => + val desc = insn.asInstanceOf[MethodInsnNode].desc + val cons = Type.getArgumentTypes(desc).length + (if (insn.getOpcode == INVOKESTATIC) 0 else 1) + val prod = if (Type.getReturnType(desc) == Type.VOID_TYPE) 0 else 1 + t(cons, prod) + + case INVOKEDYNAMIC => + val desc = insn.asInstanceOf[InvokeDynamicInsnNode].desc + val cons = Type.getArgumentTypes(desc).length + val prod = if (Type.getReturnType(desc) == Type.VOID_TYPE) 0 else 1 + t(cons, prod) + + case NEW => t(0, 1) + + case NEWARRAY | + ANEWARRAY | + ARRAYLENGTH => t(1, 1) + + case ATHROW => t(1, 0) // Frame.execute consumes one stack value + + case CHECKCAST | + INSTANCEOF => t(1, 1) // Frame.execute does push(pop()) for both of them + + case MONITORENTER | + MONITOREXIT => t(1, 0) + + case MULTIANEWARRAY => t(insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1) + + case IFNULL | + IFNONNULL => t(1, 0) + } + } + +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala new file mode 100644 index 0000000000..31710dcbee --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala @@ -0,0 +1,282 @@ +package scala.tools.nsc +package backend.jvm +package analysis + +import java.util + +import scala.annotation.switch +import scala.tools.asm.{Type, Opcodes} +import scala.tools.asm.tree.{MethodInsnNode, LdcInsnNode, AbstractInsnNode} +import scala.tools.asm.tree.analysis.{Frame, Analyzer, Interpreter, Value} +import scala.tools.nsc.backend.jvm.opt.BytecodeUtils +import BytecodeUtils._ + +/** + * Some notes on the ASM ananlyzer framework. + * + * Value + * - Abstract, needs to be implemented for each analysis. + * - Represents the desired information about local variables and stack values, for example: + * - Is this value known to be null / not null? + * - What are the instructions that could potentially have produced this value? + * + * Interpreter + * - Abstract, needs to be implemented for each analysis. Sometimes one can subclass an existing + * interpreter, e.g., SourceInterpreter or BasicInterpreter. + * - Multiple abstract methods that receive an instruction and the instruction's input values, and + * return a value representing the result of that instruction. + * - Note: due to control flow, the interpreter can be invoked multiple times for the same + * instruction, until reaching a fixed point. + * - Abstract `merge` function that computes the least upper bound of two values. Used by + * Frame.merge (see below). + * + * Frame + * - Can be used directly for many analyses, no subclass required. + * - Every frame has an array of values: one for each local variable and for each stack slot. + * - A `top` index stores the index of the current stack top + * - NOTE: for a size-2 local variable at index i, the local variable at i+1 is set to an empty + * value. However, for a size-2 value at index i on the stack, the value at i+1 holds the next + * stack value. + * - Defines the `execute(instruction)` method. + * - executing mutates the state of the frame according to the effect of the instruction + * - pop consumed values from the stack + * - pass them to the interpreter together with the instruction + * - if applicable, push the resulting value on the stack + * - Defines the `merge(otherFrame)` method + * - called by the analyzer when multiple control flow paths lead to an instruction + * - the frame at the branching instruction is merged into the current frame of the + * instruction (held by the analyzer) + * - mutates the values of the current frame, merges all values using interpreter.merge. + * + * Analyzer + * - Stores a frame for each instruction + * - `merge` function takes an instruction and a frame, merges the existing frame for that instr + * (from the frames array) with the new frame passed as argument. + * if the frame changed, puts the instruction on the work queue (fixpiont). + * - initial frame: initialized for first instr by calling interpreter.new[...]Value + * for each slot (locals and params), stored in frames[firstInstr] by calling `merge` + * - work queue of instructions (`queue` array, `top` index for next instruction to analyze) + * - analyze(method): simulate control flow. while work queue non-empty: + * - copy the state of `frames[instr]` into a local frame `current` + * - call `current.execute(instr, interpreter)`, mutating the `current` frame + * - if it's a branching instruction + * - for all potential destination instructions + * - merge the destination instruction frame with the `current` frame + * (this enqueues the destination instr if its frame changed) + * - invoke `newControlFlowEdge` (see below) + * - the analyzer also tracks active exception handlers at each instruction + * - the empty method `newControlFlowEdge` can be overridden to track control flow if required + * + * + * Some notes on nullness analysis. + * + * For an instance method, `this` is non-null at entry. So we have to return a NotNull value when + * the analyzer is initializing the first frame of a method (see above). This required a change of + * the analyzer: before it would simply call `interpreter.newValue`, where we don't have the + * required context. See https://github.com/scala/scala-asm/commit/8133d75032. + * + * After some operations we know that a certain value is not null (e.g. the receiver of an instance + * call). However, the receiver is an value on the stack and consumed while interpreting the + * instruction - so we can only gain some knowledge if we know that the receiver was an alias of + * some other local variable or stack slot. Therefore we use the AliasingFrame class. + * + * TODO: + * Finally, we'd also like to exploit the knowledge gained from `if (x == null)` tests: x is known + * to be null in one branch, not null in the other. This will make use of alias tracking as well. + * We still have to figure out how to do this exactly in the analyzer framework. + */ + +/** + * Type to represent nullness of values. + */ +sealed trait Nullness { + final def merge(other: Nullness) = if (this == other) this else Unknown +} +case object NotNull extends Nullness +case object Unknown extends Nullness +case object Null extends Nullness + +/** + * Represents the nullness state for a local variable or stack value. + * + * Note that nullness of primitive values is not tracked, it will be always [[Unknown]]. + */ +sealed trait NullnessValue extends Value { + /** + * The nullness of this value. + */ + def nullness: Nullness + + /** + * True if this value is a long or double. The Analyzer framework needs to know + * the size of each value when interpreting instructions, see `Frame.execute`. + */ + def isSize2: Boolean + /** + * The size of the slot described by this value. Cannot be 0 because no values are allocated + * for void-typed slots, see NullnessInterpreter.newValue. + **/ + def getSize: Int = if (isSize2) 2 else 1 + + def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, isSize2) +} + +object NullValue extends NullnessValue { def nullness = Null; def isSize2 = false; override def toString = "Null" } +object UnknownValue1 extends NullnessValue { def nullness = Unknown; def isSize2 = false; override def toString = "Unknown1" } +object UnknownValue2 extends NullnessValue { def nullness = Unknown; def isSize2 = true; override def toString = "Unknown2" } +object NotNullValue extends NullnessValue { def nullness = NotNull; def isSize2 = false; override def toString = "NotNull" } + +object NullnessValue { + def apply(nullness: Nullness, isSize2: Boolean): NullnessValue = { + if (nullness == Null) NullValue + else if (nullness == NotNull) NotNullValue + else if (isSize2) UnknownValue2 + else UnknownValue1 + } + + def apply(nullness: Nullness, insn: AbstractInsnNode): NullnessValue = { + apply(nullness, isSize2 = BytecodeUtils.instructionResultSize(insn) == 2) + } +} + +final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) { + def newValue(tp: Type): NullnessValue = { + // ASM loves giving semantics to null. The behavior here is the same as in SourceInterpreter, + // which is provided by the framework. + // + // (1) For the void type, the ASM framework expects newValue to return `null`. + // Also, the Frame.returnValue field is `null` for methods with return type void. + // Example callsite passing VOID_TYPE: in Analyzer, `newValue(Type.getReturnType(m.desc))`. + // + // (2) `tp` may also be `null`. When creating the initial frame, the analyzer invokes + // `newValue(null)` for each local variable. We have to return a value of size 1. + if (tp == Type.VOID_TYPE) null // (1) + else NullnessValue(Unknown, isSize2 = tp != null /*(2)*/ && tp.getSize == 2 ) + } + + override def newParameterValue(isInstanceMethod: Boolean, local: Int, tp: Type): NullnessValue = { + // For instance methods, the `this` parameter is known to be not null. + if (isInstanceMethod && local == 0) NullnessValue(NotNull, isSize2 = false) + else super.newParameterValue(isInstanceMethod, local, tp) + } + + def newOperation(insn: AbstractInsnNode): NullnessValue = { + val nullness = (insn.getOpcode: @switch) match { + case Opcodes.ACONST_NULL => Null + + case Opcodes.LDC => insn.asInstanceOf[LdcInsnNode].cst match { + case _: String | _: Type => NotNull + case _ => Unknown + } + + case _ => Unknown + } + + // for Opcodes.NEW, we use Unknown. The value will become NotNull after the constructor call. + NullnessValue(nullness, insn) + } + + def copyOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = value + + def unaryOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = (insn.getOpcode: @switch) match { + case Opcodes.CHECKCAST => value + + case Opcodes.NEWARRAY | + Opcodes.ANEWARRAY => NullnessValue(NotNull, isSize2 = false) + + case _ => NullnessValue(Unknown, insn) + } + + def binaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue): NullnessValue = { + NullnessValue(Unknown, insn) + } + + def ternaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue, value3: NullnessValue): NullnessValue = { + NullnessValue(Unknown, isSize2 = false) + } + + def naryOperation(insn: AbstractInsnNode, values: util.List[_ <: NullnessValue]): NullnessValue = (insn.getOpcode: @switch) match { + case Opcodes.MULTIANEWARRAY => + NullnessValue(NotNull, isSize2 = false) + + case _ => + // TODO: use a list of methods that are known to return non-null values + NullnessValue(Unknown, insn) + } + + def returnOperation(insn: AbstractInsnNode, value: NullnessValue, expected: NullnessValue): Unit = () + + def merge(a: NullnessValue, b: NullnessValue): NullnessValue = a merge b +} + +class NullnessFrame(nLocals: Int, nStack: Int) extends AliasingFrame[NullnessValue](nLocals, nStack) { + // Auxiliary constructor required for implementing `NullnessAnalyzer.newFrame` + def this(src: Frame[_ <: NullnessValue]) { + this(src.getLocals, src.getMaxStackSize) + init(src) + } + + override def execute(insn: AbstractInsnNode, interpreter: Interpreter[NullnessValue]): Unit = { + import Opcodes._ + + // get the object id of the object that is known to be not-null after this operation + val nullCheckedAliasId: Long = (insn.getOpcode: @switch) match { + case IALOAD | + LALOAD | + FALOAD | + DALOAD | + AALOAD | + BALOAD | + CALOAD | + SALOAD => + aliasId(this.stackTop - 1) + + case IASTORE | + FASTORE | + AASTORE | + BASTORE | + CASTORE | + SASTORE | + LASTORE | + DASTORE => + aliasId(this.stackTop - 2) + + case GETFIELD => + aliasId(this.stackTop) + + case PUTFIELD => + aliasId(this.stackTop - 1) + + case INVOKEVIRTUAL | + INVOKESPECIAL | + INVOKEINTERFACE => + val desc = insn.asInstanceOf[MethodInsnNode].desc + val numArgs = Type.getArgumentTypes(desc).length + aliasId(this.stackTop - numArgs) + + case ARRAYLENGTH | + MONITORENTER | + MONITOREXIT => + aliasId(this.stackTop) + + case _ => + -1 + } + + super.execute(insn, interpreter) + + if (nullCheckedAliasId != -1) { + for (i <- valuesWithAliasId(nullCheckedAliasId)) + this.setValue(i, NotNullValue) + } + } +} + +/** + * This class is required to override the `newFrame` methods, which makes makes sure the analyzer + * uses NullnessFrames. + */ +class NullnessAnalyzer extends Analyzer[NullnessValue](new NullnessInterpreter) { + override def newFrame(nLocals: Int, nStack: Int): NullnessFrame = new NullnessFrame(nLocals, nStack) + override def newFrame(src: Frame[_ <: NullnessValue]): NullnessFrame = new NullnessFrame(src) +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala index 201ab15177..9bd016f964 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala @@ -170,6 +170,8 @@ object BytecodeUtils { new InsnNode(op) } + def instructionResultSize(instruction: AbstractInsnNode) = InstructionResultSize(instruction) + def labelReferences(method: MethodNode): Map[LabelNode, Set[AnyRef]] = { val res = mutable.Map.empty[LabelNode, Set[AnyRef]] def add(l: LabelNode, ref: AnyRef) = if (res contains l) res(l) = res(l) + ref else res(l) = Set(ref) @@ -328,13 +330,38 @@ object BytecodeUtils { class AsmAnalyzer[V <: Value](methodNode: MethodNode, classInternalName: InternalName, interpreter: Interpreter[V] = new BasicInterpreter) { val analyzer = new Analyzer(interpreter) analyzer.analyze(classInternalName, methodNode) - def frameAt(instruction: AbstractInsnNode): Frame[V] = analyzer.getFrames()(methodNode.instructions.indexOf(instruction)) + def frameAt(instruction: AbstractInsnNode): Frame[V] = analyzer.frameAt(instruction, methodNode) + } + + implicit class AnalyzerExtensions[V <: Value](val analyzer: Analyzer[V]) extends AnyVal { + def frameAt(instruction: AbstractInsnNode, methodNode: MethodNode): Frame[V] = analyzer.getFrames()(methodNode.instructions.indexOf(instruction)) } - implicit class `frame extensions`[V <: Value](val frame: Frame[V]) extends AnyVal { - def peekDown(n: Int): V = { - val topIndex = frame.getStackSize - 1 - frame.getStack(topIndex - n) + implicit class FrameExtensions[V <: Value](val frame: Frame[V]) extends AnyVal { + /** + * The value `n` positions down the stack. + */ + def peekStack(n: Int): V = frame.getStack(frame.getStackSize - 1 - n) + + /** + * The index of the current stack top. + */ + def stackTop = frame.getLocals + frame.getStackSize - 1 + + /** + * Gets the value at slot i, where i may be a local or a stack index. + */ + def getValue(i: Int): V = { + if (i < frame.getLocals) frame.getLocal(i) + else frame.getStack(i - frame.getLocals) + } + + /** + * Sets the value at slot i, where i may be a local or a stack index. + */ + def setValue(i: Int, value: V): Unit = { + if (i < frame.getLocals) frame.setLocal(i, value) + else frame.setStack(i - frame.getLocals, value) } } } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala index 028f0f8fa6..0932564b1f 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala @@ -8,12 +8,15 @@ package backend.jvm package opt import scala.reflect.internal.util.{NoPosition, Position} +import scala.tools.asm.tree.analysis.{Value, Analyzer, BasicInterpreter} +import scala.tools.asm.{Opcodes, Type} import scala.tools.asm.tree._ import scala.collection.convert.decorateAsScala._ -import scala.tools.nsc.backend.jvm.BTypes.{MethodInlineInfo, InternalName} +import scala.tools.nsc.backend.jvm.BTypes.InternalName import scala.tools.nsc.backend.jvm.BackendReporting._ -import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.AsmAnalyzer +import scala.tools.nsc.backend.jvm.analysis.{NotNull, NullnessAnalyzer} import ByteCodeRepository.{Source, CompilationUnit} +import BytecodeUtils._ class CallGraph[BT <: BTypes](val btypes: BT) { import btypes._ @@ -93,12 +96,25 @@ class CallGraph[BT <: BTypes](val btypes: BT) { // TODO: run dataflow analyses to make the call graph more precise // - producers to get forwarded parameters (ForwardedParam) // - typeAnalysis for more precise argument types, more precise callee - // - nullAnalysis to skip emitting the receiver-null-check when inlining - // TODO: for now we run a basic analyzer to get the stack height at the call site. - // once we run a more elaborate analyzer (types, nullness), we can get the stack height out of there. + // For now we run a NullnessAnalyzer. It is used to determine if the receiver of an instance + // call is known to be not-null, in which case we don't have to emit a null check when inlining. + // It is also used to get the stack height at the call site. localOpt.minimalRemoveUnreachableCode(methodNode, definingClass.internalName) - val analyzer = new AsmAnalyzer(methodNode, definingClass.internalName) + + val analyzer: Analyzer[_ <: Value] = { + if (compilerSettings.YoptNullnessTracking) new NullnessAnalyzer + else new Analyzer(new BasicInterpreter) + } + analyzer.analyze(definingClass.internalName, methodNode) + + def receiverNotNullByAnalysis(call: MethodInsnNode, numArgs: Int) = analyzer match { + case nullnessAnalyzer: NullnessAnalyzer => + val frame = nullnessAnalyzer.frameAt(call, methodNode) + frame.getStack(frame.getStackSize - 1 - numArgs).nullness == NotNull + + case _ => false + } methodNode.instructions.iterator.asScala.collect({ case call: MethodInsnNode => @@ -126,13 +142,19 @@ class CallGraph[BT <: BTypes](val btypes: BT) { Nil } + val receiverNotNull = call.getOpcode == Opcodes.INVOKESTATIC || { + val numArgs = Type.getArgumentTypes(call.desc).length + receiverNotNullByAnalysis(call, numArgs) + } + Callsite( callsiteInstruction = call, callsiteMethod = methodNode, callsiteClass = definingClass, callee = callee, argInfos = argInfos, - callsiteStackHeight = analyzer.frameAt(call).getStackSize, + callsiteStackHeight = analyzer.frameAt(call, methodNode).getStackSize, + receiverKnownNotNull = receiverNotNull, callsitePosition = callsitePositions.getOrElse(call, NoPosition) ) }).toList @@ -154,7 +176,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { */ final case class Callsite(callsiteInstruction: MethodInsnNode, callsiteMethod: MethodNode, callsiteClass: ClassBType, callee: Either[OptimizerWarning, Callee], argInfos: List[ArgInfo], - callsiteStackHeight: Int, callsitePosition: Position) { + callsiteStackHeight: Int, receiverKnownNotNull: Boolean, callsitePosition: Position) { override def toString = "Invocation of" + s" ${callee.map(_.calleeDeclarationClass.internalName).getOrElse("?")}.${callsiteInstruction.name + callsiteInstruction.desc}" + diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala index ac5c9ce2e6..814c78b69c 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala @@ -49,7 +49,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { if (callGraph.callsites contains request.callsiteInstruction) { val r = inline(request.callsiteInstruction, request.callsiteStackHeight, request.callsiteMethod, request.callsiteClass, callee.callee, callee.calleeDeclarationClass, - receiverKnownNotNull = false, keepLineNumbers = false) + request.receiverKnownNotNull, keepLineNumbers = false) for (warning <- r) { if ((callee.annotatedInline && btypes.compilerSettings.YoptWarningEmitAtInlineFailed) || warning.emitWarning(compilerSettings)) { @@ -89,7 +89,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { */ def selectCallsitesForInlining: List[Callsite] = { callsites.valuesIterator.filter({ - case callsite @ Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, warning)), _, _, pos) => + case callsite @ Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, warning)), _, _, _, pos) => val res = doInlineCallsite(callsite) if (!res) { @@ -112,7 +112,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { res - case Callsite(ins, _, _, Left(warning), _, _, pos) => + case Callsite(ins, _, _, Left(warning), _, _, _, pos) => if (warning.emitWarning(compilerSettings)) backendReporting.inlinerWarning(pos, s"failed to determine if ${ins.name} should be inlined:\n$warning") false @@ -123,7 +123,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { * The current inlining heuristics are simple: inline calls to methods annotated @inline. */ def doInlineCallsite(callsite: Callsite): Boolean = callsite match { - case Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, warning)), _, _, pos) => + case Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, warning)), _, _, _, pos) => if (compilerSettings.YoptInlineHeuristics.value == "everything") safeToInline else annotatedInline && safeToInline @@ -189,7 +189,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { // there's no need to run eliminateUnreachableCode here. building the call graph does that // already, no code can become unreachable in the meantime. val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new SourceInterpreter) - val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekDown(traitMethodArgumentTypes.length) + val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekStack(traitMethodArgumentTypes.length) for (i <- receiverValue.insns.asScala) { val cast = new TypeInsnNode(CHECKCAST, selfParamType.internalName) callsite.callsiteMethod.instructions.insert(i, cast) @@ -215,6 +215,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { calleeInfoWarning = infoWarning)), argInfos = Nil, callsiteStackHeight = callsite.callsiteStackHeight, + receiverKnownNotNull = callsite.receiverKnownNotNull, callsitePosition = callsite.callsitePosition ) callGraph.callsites(newCallsiteInstruction) = staticCallsite @@ -400,7 +401,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { val inlinedReturn = instructionMap(originalReturn) val returnReplacement = new InsnList - def drop(slot: Int) = returnReplacement add getPop(frame.peekDown(slot).getSize) + def drop(slot: Int) = returnReplacement add getPop(frame.peekStack(slot).getSize) // for non-void methods, store the stack top into the return local variable if (hasReturnValue) { @@ -444,6 +445,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { callee = originalCallsite.callee, argInfos = Nil, // TODO: re-compute argInfos for new destination (once we actually compute them) callsiteStackHeight = callsiteStackHeight + originalCallsite.callsiteStackHeight, + receiverKnownNotNull = originalCallsite.receiverKnownNotNull, callsitePosition = originalCallsite.callsitePosition ) diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/InstructionResultSize.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/InstructionResultSize.scala new file mode 100644 index 0000000000..8d744f6d13 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/InstructionResultSize.scala @@ -0,0 +1,240 @@ +package scala.tools.nsc.backend.jvm.opt + +import scala.annotation.switch +import scala.tools.asm.{Handle, Type, Opcodes} +import scala.tools.asm.tree._ + +object InstructionResultSize { + import Opcodes._ + def apply(instruction: AbstractInsnNode): Int = (instruction.getOpcode: @switch) match { + // The order of opcodes is (almost) the same as in Opcodes.java + case ACONST_NULL => 1 + + case ICONST_M1 | + ICONST_0 | + ICONST_1 | + ICONST_2 | + ICONST_3 | + ICONST_4 | + ICONST_5 => 1 + + case LCONST_0 | + LCONST_1 => 2 + + case FCONST_0 | + FCONST_1 | + FCONST_2 => 1 + + case DCONST_0 | + DCONST_1 => 2 + + case BIPUSH | + SIPUSH => 1 + + case LDC => + instruction.asInstanceOf[LdcInsnNode].cst match { + case _: java.lang.Integer | + _: java.lang.Float | + _: String | + _: Type | + _: Handle => 1 + + case _: java.lang.Long | + _: java.lang.Double => 2 + } + + case ILOAD | + FLOAD | + ALOAD => 1 + + case LLOAD | + DLOAD => 2 + + case IALOAD | + FALOAD | + AALOAD | + BALOAD | + CALOAD | + SALOAD => 1 + + case LALOAD | + DALOAD => 2 + + case ISTORE | + LSTORE | + FSTORE | + DSTORE | + ASTORE => 0 + + case IASTORE | + LASTORE | + FASTORE | + DASTORE | + AASTORE | + BASTORE | + CASTORE | + SASTORE => 0 + + case POP | + POP2 => 0 + + case DUP | + DUP_X1 | + DUP_X2 | + DUP2 | + DUP2_X1 | + DUP2_X2 | + SWAP => throw new IllegalArgumentException("Can't compute the size of DUP/SWAP without knowing what's on stack top") + + case IADD | + FADD => 1 + + case LADD | + DADD => 2 + + case ISUB | + FSUB => 1 + + case LSUB | + DSUB => 2 + + case IMUL | + FMUL => 1 + + case LMUL | + DMUL => 2 + + case IDIV | + FDIV => 1 + + case LDIV | + DDIV => 2 + + case IREM | + FREM => 1 + + case LREM | + DREM => 2 + + case INEG | + FNEG => 1 + + case LNEG | + DNEG => 2 + + case ISHL | + ISHR => 1 + + case LSHL | + LSHR => 2 + + case IUSHR => 1 + + case LUSHR => 2 + + case IAND | + IOR | + IXOR => 1 + + case LAND | + LOR | + LXOR => 2 + + case IINC => 1 + + case I2F | + L2I | + L2F | + F2I | + D2I | + D2F | + I2B | + I2C | + I2S => 1 + + case I2L | + I2D | + L2D | + F2L | + F2D | + D2L => 2 + + case LCMP | + FCMPL | + FCMPG | + DCMPL | + DCMPG => 1 + + case IFEQ | + IFNE | + IFLT | + IFGE | + IFGT | + IFLE => 0 + + case IF_ICMPEQ | + IF_ICMPNE | + IF_ICMPLT | + IF_ICMPGE | + IF_ICMPGT | + IF_ICMPLE | + IF_ACMPEQ | + IF_ACMPNE => 0 + + case GOTO => 0 + + case JSR => throw new IllegalArgumentException("Subroutines are not supported.") + + case RET => 0 + + case TABLESWITCH | + LOOKUPSWITCH => 0 + + case IRETURN | + FRETURN | + ARETURN => 1 + + case LRETURN | + DRETURN => 2 + + case RETURN => 0 + + case GETSTATIC => Type.getType(instruction.asInstanceOf[FieldInsnNode].desc).getSize + + case PUTSTATIC => 0 + + case GETFIELD => Type.getType(instruction.asInstanceOf[FieldInsnNode].desc).getSize + + case PUTFIELD => 0 + + case INVOKEVIRTUAL | + INVOKESPECIAL | + INVOKESTATIC | + INVOKEINTERFACE => + val desc = instruction.asInstanceOf[MethodInsnNode].desc + Type.getReturnType(desc).getSize + + case INVOKEDYNAMIC => + val desc = instruction.asInstanceOf[InvokeDynamicInsnNode].desc + Type.getReturnType(desc).getSize + + case NEW => 1 + + case NEWARRAY | + ANEWARRAY | + ARRAYLENGTH => 1 + + case ATHROW => 0 + + case CHECKCAST | + INSTANCEOF => 1 + + case MONITORENTER | + MONITOREXIT => 0 + + case MULTIANEWARRAY => 1 + + case IFNULL | + IFNONNULL => 0 + } +} diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 35ee889c58..953e43eaca 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -234,15 +234,16 @@ trait ScalaSettings extends AbsScalaSettings val emptyLineNumbers = Choice("empty-line-numbers", "Eliminate unnecessary line number information.") val emptyLabels = Choice("empty-labels", "Eliminate and collapse redundant labels in the bytecode.") val compactLocals = Choice("compact-locals", "Eliminate empty slots in the sequence of local variables.") - val inlineProject = Choice("inline-project", "Inline only methods defined in the files being compiled") - val inlineGlobal = Choice("inline-global", "Inline methods from any source, including classfiles on the compile classpath") + val nullnessTracking = Choice("nullness-tracking", "Track nullness / non-nullness of local variables and apply optimizations.") + val inlineProject = Choice("inline-project", "Inline only methods defined in the files being compiled.") + val inlineGlobal = Choice("inline-global", "Inline methods from any source, including classfiles on the compile classpath.") val lNone = Choice("l:none", "Don't enable any optimizations.") private val defaultChoices = List(unreachableCode) val lDefault = Choice("l:default", "Enable default optimizations: "+ defaultChoices.mkString(","), expandsTo = defaultChoices) - private val methodChoices = List(unreachableCode, simplifyJumps, emptyLineNumbers, emptyLabels, compactLocals) + private val methodChoices = List(unreachableCode, simplifyJumps, emptyLineNumbers, emptyLabels, compactLocals, nullnessTracking) val lMethod = Choice("l:method", "Enable intra-method optimizations: "+ methodChoices.mkString(","), expandsTo = methodChoices) private val projectChoices = List(lMethod, inlineProject) @@ -264,6 +265,7 @@ trait ScalaSettings extends AbsScalaSettings def YoptEmptyLineNumbers = Yopt.contains(YoptChoices.emptyLineNumbers) def YoptEmptyLabels = Yopt.contains(YoptChoices.emptyLabels) def YoptCompactLocals = Yopt.contains(YoptChoices.compactLocals) + def YoptNullnessTracking = Yopt.contains(YoptChoices.nullnessTracking) def YoptInlineProject = Yopt.contains(YoptChoices.inlineProject) def YoptInlineGlobal = Yopt.contains(YoptChoices.inlineGlobal) |