diff options
13 files changed, 1364 insertions, 26 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) diff --git a/test/files/neg/inlineMaxSize.check b/test/files/neg/inlineMaxSize.check index d218a8b6e2..9d790e154c 100644 --- a/test/files/neg/inlineMaxSize.check +++ b/test/files/neg/inlineMaxSize.check @@ -2,8 +2,8 @@ inlineMaxSize.scala:7: warning: C::i()I is annotated @inline but could not be in The size of the callsite method C::j()I would exceed the JVM method size limit after inlining C::i()I. - @inline final def j = i + i - ^ + @inline final def j = i + i + i + ^ error: No warnings can be incurred under -Xfatal-warnings. one warning found one error found diff --git a/test/files/neg/inlineMaxSize.scala b/test/files/neg/inlineMaxSize.scala index 16dc0d9538..9d2db1a357 100644 --- a/test/files/neg/inlineMaxSize.scala +++ b/test/files/neg/inlineMaxSize.scala @@ -4,5 +4,5 @@ class C { @inline final def g = f + f + f + f + f + f + f + f + f + f @inline final def h = g + g + g + g + g + g + g + g + g + g @inline final def i = h + h + h + h + h + h + h + h + h + h - @inline final def j = i + i + @inline final def j = i + i + i } diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala new file mode 100644 index 0000000000..3a85f03da2 --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala @@ -0,0 +1,231 @@ +package scala.tools.nsc +package backend.jvm +package analysis + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test +import scala.tools.asm.Opcodes._ +import org.junit.Assert._ + +import CodeGenTools._ +import scala.tools.asm.tree.{AbstractInsnNode, MethodNode} +import scala.tools.nsc.backend.jvm.BTypes._ +import scala.tools.partest.ASMConverters +import ASMConverters._ +import scala.tools.testing.ClearAfterClass +import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._ +import AsmUtils._ + +import scala.collection.convert.decorateAsScala._ + +object NullnessAnalyzerTest extends ClearAfterClass.Clearable { + var noOptCompiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:none") + + def clear(): Unit = { + noOptCompiler = null + } +} + +@RunWith(classOf[JUnit4]) +class NullnessAnalyzerTest extends ClearAfterClass { + ClearAfterClass.stateToClear = NullnessAnalyzerTest + val noOptCompiler = NullnessAnalyzerTest.noOptCompiler + + def newNullnessAnalyzer(methodNode: MethodNode, classInternalName: InternalName = "C"): NullnessAnalyzer = { + val nullnessAnalyzer = new NullnessAnalyzer + nullnessAnalyzer.analyze(classInternalName, methodNode) + nullnessAnalyzer + } + + /** + * Instructions that match `query` when textified. + * If `query` starts with a `+`, the next instruction is returned. + */ + def findInstr(method: MethodNode, query: String): List[AbstractInsnNode] = { + val useNext = query(0) == '+' + val instrPart = if (useNext) query.drop(1) else query + val insns = method.instructions.iterator.asScala.find(i => textify(i) contains instrPart).toList + if (useNext) insns.map(_.getNext) else insns + } + + def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: Nullness): Unit = { + for (i <- findInstr(method, query)) { + val r = analyzer.frameAt(i, method).getValue(index).nullness + assertTrue(s"Expected: $nullness, found: $r. At instr ${textify(i)}", nullness == r) + } + } + + // debug / helper for writing tests + def showAllNullnessFrames(analyzer: NullnessAnalyzer, method: MethodNode): String = { + val instrLength = method.instructions.iterator.asScala.map(textify(_).length).max + val lines = for (i <- method.instructions.iterator.asScala) yield { + val f = analyzer.frameAt(i, method) + val frameString = { + if (f == null) "null" + else (0 until (f.getLocals + f.getStackSize)).iterator + .map(f.getValue(_).toString) + .map(s => "%8s".format(s)) + .zipWithIndex.map({case (s, i) => s"$i: $s"}) + .mkString(", ") + } + ("%"+ instrLength +"s: %s").format(textify(i), frameString) + } + lines.mkString("\n") + } + + @Test + def showNullnessFramesTest(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = this.toString") + + // NOTE: the frame for an instruction represents the state *before* executing that instr. + // So in the frame for `ALOAD 0`, the stack is still empty. + + val res = + """ L0: 0: NotNull + | LINENUMBER 1 L0: 0: NotNull + | ALOAD 0: 0: NotNull + |INVOKEVIRTUAL java/lang/Object.toString ()Ljava/lang/String;: 0: NotNull, 1: NotNull + | ARETURN: 0: NotNull, 1: Unknown1 + | L0: null""".stripMargin + assertEquals(showAllNullnessFrames(newNullnessAnalyzer(m), m), res) + } + + @Test + def thisNonNull(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = this.toString") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "ALOAD 0", 0, NotNull) + } + + @Test + def instanceMethodCall(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f(a: String) = a.trim") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "INVOKEVIRTUAL java/lang/String.trim", 1, Unknown) + testNullness(a, m, "ARETURN", 1, NotNull) + } + + @Test + def constructorCall(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = { val a = new Object; a.toString }") + val a = newNullnessAnalyzer(m) + + // for reference, the output of showAllNullnessFrames(a, m) - note that the frame represents the state *before* executing the instr. + // NEW java/lang/Object: 0: NotNull, 1: Unknown + // DUP: 0: NotNull, 1: Unknown, 2: Unknown + // INVOKESPECIAL java/lang/Object.<init>: 0: NotNull, 1: Unknown, 2: Unknown, 3: Unknown + // ASTORE 1: 0: NotNull, 1: Unknown, 2: NotNull + // ALOAD 1: 0: NotNull, 1: NotNull + // INVOKEVIRTUAL java/lang/Object.toString: 0: NotNull, 1: NotNull, 2: NotNull + // ARETURN: 0: NotNull, 1: NotNull, 2: Unknown + + for ((insn, index, nullness) <- List( + ("+NEW", 2, Unknown), // new value at slot 2 on the stack + ("+DUP", 3, Unknown), + ("+INVOKESPECIAL java/lang/Object", 2, NotNull), // after calling the initializer on 3, the value at 2 becomes NotNull + ("ASTORE 1", 1, Unknown), // before the ASTORE 1, nullness of the value in local 1 is Unknown + ("+ASTORE 1", 1, NotNull), // after storing the value at 2 in local 1, the local 1 is NotNull + ("+ALOAD 1", 2, NotNull), // loading the value 1 puts a NotNull value on the stack (at 2) + ("+INVOKEVIRTUAL java/lang/Object.toString", 2, Unknown) // nullness of value returned by `toString` is Unknown + )) testNullness(a, m, insn, index, nullness) + } + + @Test + def explicitNull(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = { var a: Object = null; a }") + val a = newNullnessAnalyzer(m) + for ((insn, index, nullness) <- List( + ("+ACONST_NULL", 2, Null), + ("+ASTORE 1", 1, Null), + ("+ALOAD 1", 2, Null) + )) testNullness(a, m, insn, index, nullness) + } + + @Test + def stringLiteralsNotNull(): Unit = { + val List(m) = compileMethods(noOptCompiler)("""def f = { val a = "hi"; a.trim }""") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "+ASTORE 1", 1, NotNull) + } + + @Test + def newArraynotNull() { + val List(m) = compileMethods(noOptCompiler)("def f = { val a = new Array[Int](2); a(0) }") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "+NEWARRAY T_INT", 2, NotNull) // new array on stack + testNullness(a, m, "+ASTORE 1", 1, NotNull) // local var (a) + } + + @Test + def aliasBranching(): Unit = { + val code = + """def f(o: Object) = { + | var a: Object = o // a and o are aliases + | var b: Object = null + | var c: Object = null + | var d: Object = o + | if ("".trim == "") { + | b = o + | c = o // a, o, b, aliases + | d = null + | } else { + | b = a // a, o, b aliases + | d = null + | } + | b.toString // a, o, b aliases (so they become NotNull), but not c + | // d is null here, assinged in both branches. + |} + """.stripMargin + val List(m) = compileMethods(noOptCompiler)(code) + val a = newNullnessAnalyzer(m) + + val trim = "INVOKEVIRTUAL java/lang/String.trim" + val toSt = "INVOKEVIRTUAL java/lang/Object.toString" + val end = s"+$toSt" + for ((insn, index, nullness) <- List( + (trim, 0, NotNull), // this + (trim, 1, Unknown), // parameter o + (trim, 2, Unknown), // a + (trim, 3, Null), // b + (trim, 4, Null), // c + (trim, 5, Unknown), // d + + (toSt, 2, Unknown), // a, still the same + (toSt, 3, Unknown), // b, was re-assinged in both branches to Unknown + (toSt, 4, Unknown), // c, was re-assigned in one branch to Unknown + (toSt, 5, Null), // d, was assigned to null in both branches + + (end, 2, NotNull), // a, NotNull (alias of b) + (end, 3, NotNull), // b, receiver of toString + (end, 4, Unknown), // c, no change (not an alias of b) + (end, 5, Null) // d, no change + )) testNullness(a, m, insn, index, nullness) + } + + @Test + def testInstanceOf(): Unit = { + val code = + """def f(a: Object) = { + | val x = a + | x.isInstanceOf[Throwable] // x and a remain unknown - INSTANCEOF doesn't throw a NPE on null + | x.toString // x and a are not null + | a.asInstanceOf[String].trim // the stack value (LOAD of local a) is still not-null after the CHECKCAST + |} + """.stripMargin + val List(m) = compileMethods(noOptCompiler)(code) + val a = newNullnessAnalyzer(m) + + val instof = "+INSTANCEOF" + val tost = "+INVOKEVIRTUAL java/lang/Object.toString" + val trim = "INVOKEVIRTUAL java/lang/String.trim" + + for ((insn, index, nullness) <- List( + (instof, 1, Unknown), // a after INSTANCEOF + (instof, 2, Unknown), // x after INSTANCEOF + (tost, 1, NotNull), + (tost, 2, NotNull), + (trim, 3, NotNull) // receiver at `trim` + )) testNullness(a, m, insn, index, nullness) + } +} diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala index 0fc3601603..b8c5f85c49 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala @@ -975,4 +975,20 @@ class InlinerTest extends ClearAfterClass { val List(c) = compile(code) assertInvoke(getSingleMethod(c, "t"), "java/lang/Error", "<init>") } + + @Test + def noRedunantNullChecks(): Unit = { + val code = + """class C { + | @inline final def f: String = "hai!" + | def t(c: C) = {c.f; c.f} // null check on the first, but not the second + |} + """.stripMargin + + val List(c) = compile(code) + val t = getSingleMethod(c, "t").instructions + assertNoInvoke(t) + assert(2 == t.collect({case Ldc(_, "hai!") => }).size) // twice the body of f + assert(1 == t.collect({case Jump(IFNONNULL, _) => }).size) // one single null check + } } diff --git a/versions.properties b/versions.properties index 406690861e..a7ec8caedc 100644 --- a/versions.properties +++ b/versions.properties @@ -33,7 +33,7 @@ scala-swing.version.number=1.0.2 akka-actor.version.number=2.3.10 actors-migration.version.number=1.1.0 jline.version=2.12.1 -scala-asm.version=5.0.3-scala-3 +scala-asm.version=5.0.4-scala-1 # external modules, used internally (not shipped) partest.version.number=1.0.7 |