diff options
8 files changed, 1237 insertions, 8 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..9494553ce1 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala @@ -0,0 +1,247 @@ +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.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) + + val (consumed, produced) = InstructionStackEffect(insn, this) // needs to be called before super.execute, see its doc + 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..3d6c53765e --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala @@ -0,0 +1,248 @@ +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._ + +object InstructionStackEffect { + /** + * 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 => (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 => (0, 1) + + case IALOAD | + LALOAD | + FALOAD | + DALOAD | + AALOAD | + BALOAD | + CALOAD | + SALOAD => (2, 1) + + case ISTORE | + LSTORE | + FSTORE | + DSTORE | + ASTORE => (1, 0) + + case IASTORE | + LASTORE | + FASTORE | + DASTORE | + AASTORE | + BASTORE | + CASTORE | + SASTORE => (3, 0) + + case POP => (1, 0) + + case POP2 => + val isSize2 = peekStack(0).getSize == 2 + if (isSize2) (1, 0) else (2, 0) + + case DUP => (0, 1) + + case DUP_X1 => (2, 3) + + case DUP_X2 => + val isSize2 = peekStack(1).getSize == 2 + if (isSize2) (2, 3) else (3, 4) + + case DUP2 => + val isSize2 = peekStack(0).getSize == 2 + if (isSize2) (0, 1) else (0, 2) + + case DUP2_X1 => + val isSize2 = peekStack(0).getSize == 2 + if (isSize2) (2, 3) else (3, 4) + + case DUP2_X2 => + val v1isSize2 = peekStack(0).getSize == 2 + if (v1isSize2) { + val v2isSize2 = peekStack(1).getSize == 2 + if (v2isSize2) (2, 3) else (3, 4) + } else { + val v3isSize2 = peekStack(2).getSize == 2 + if (v3isSize2) (3, 5) else (4, 6) + } + + case SWAP => (2, 2) + + case IADD | + LADD | + FADD | + DADD | + ISUB | + LSUB | + FSUB | + DSUB | + IMUL | + LMUL | + FMUL | + DMUL | + IDIV | + LDIV | + FDIV | + DDIV | + IREM | + LREM | + FREM | + DREM => (2, 1) + + case INEG | + LNEG | + FNEG | + DNEG => (1, 1) + + case ISHL | + LSHL | + ISHR | + LSHR | + IUSHR | + LUSHR | + IAND | + LAND | + IOR | + LOR | + IXOR | + LXOR => (2, 1) + + case IINC => (0, 0) + + case I2L | + I2F | + I2D | + L2I | + L2F | + L2D | + F2I | + F2L | + F2D | + D2I | + D2L | + D2F | + I2B | + I2C | + I2S => (1, 1) + + case LCMP | + FCMPL | + FCMPG | + DCMPL | + DCMPG => (2, 1) + + case IFEQ | + IFNE | + IFLT | + IFGE | + IFGT | + IFLE => (1, 0) + + case IF_ICMPEQ | + IF_ICMPNE | + IF_ICMPLT | + IF_ICMPGE | + IF_ICMPGT | + IF_ICMPLE | + IF_ACMPEQ | + IF_ACMPNE => (2, 0) + + case GOTO => (0, 0) + + case JSR => (0, 1) + + case RET => (0, 0) + + case TABLESWITCH | + LOOKUPSWITCH => (1, 0) + + case IRETURN | + LRETURN | + FRETURN | + DRETURN | + ARETURN => (frame.getStackSize, 0) + + case RETURN => (frame.getStackSize, 0) + + case GETSTATIC => (0, 1) + + case PUTSTATIC => (1, 0) + + case GETFIELD => (1, 1) + + case PUTFIELD => (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 + (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 + (cons, prod) + + case NEW => (0, 1) + + case NEWARRAY | + ANEWARRAY | + ARRAYLENGTH => (1, 1) + + case ATHROW => (frame.getStackSize, 0) + + case CHECKCAST => (0, 0) + + case INSTANCEOF => (1, 1) + + case MONITORENTER | + MONITOREXIT => (1, 0) + + case MULTIANEWARRAY => (insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1) + + case IFNULL | + IFNONNULL => (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..18c17bc992 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala @@ -0,0 +1,262 @@ +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]]. + * + * @param nullness The nullness of this value. + * @param longOrDouble 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`. + */ +final case class NullnessValue(nullness: Nullness, longOrDouble: Boolean) extends Value { + def this(nullness: Nullness, insn: AbstractInsnNode) = this(nullness, longOrDouble = BytecodeUtils.instructionResultSize(insn) == 2) + + /** + * 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 (longOrDouble) 2 else 1 + + def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, longOrDouble) +} + +object NullnessValue { + def apply(nullness: Nullness, insn: AbstractInsnNode) = new NullnessValue(nullness, insn) +} + +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, longOrDouble = 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, longOrDouble = 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.NEWARRAY | + Opcodes.ANEWARRAY => NullnessValue(NotNull, longOrDouble = 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, longOrDouble = false) + } + + def naryOperation(insn: AbstractInsnNode, values: util.List[_ <: NullnessValue]): NullnessValue = (insn.getOpcode: @switch) match { + case Opcodes.MULTIANEWARRAY => + NullnessValue(NotNull, longOrDouble = 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, this.getValue(i).copy(nullness = NotNull)) + } + } +} + +/** + * 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..314105da44 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 AnalyzerExtendsions[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.getMaxStackSize - 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/Inliner.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala index ac5c9ce2e6..3aca15da69 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala @@ -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) @@ -400,7 +400,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) { 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/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..92574329db --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala @@ -0,0 +1,205 @@ +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 f.toString.split("NullnessValue").iterator + .map(_.trim).filter(_.nonEmpty) + .map(s => "%7s".format(s.replaceAll("""\((.*),false\)""", "$1"))) + .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: Unknown + | L0: null""".stripMargin + assertTrue(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) + } +} 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 |