From 57be8a33ebbc8e7a7d64404fe5db74ef895c5891 Mon Sep 17 00:00:00 2001 From: Lukas Rytz Date: Thu, 30 Apr 2015 14:11:57 +0200 Subject: Nullness Analysis Tracks nullness of values using an ASM analyzer. Tracking nullness requires alias tracking for local variables and stack values. For example, after an instance call, local variables that point to the same object as the receiver are treated not-null. --- .../jvm/analysis/NullnessAnalyzerTest.scala | 205 +++++++++++++++++++++ 1 file changed, 205 insertions(+) create mode 100644 test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala (limited to 'test') 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.: 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) + } +} -- cgit v1.2.3 From f4381866a8560ed65ce411c2f28ffd9b4df945e2 Mon Sep 17 00:00:00 2001 From: Lukas Rytz Date: Fri, 22 May 2015 17:34:06 +0200 Subject: Enable nullness analysis in the inliner When inlining an instance call, the inliner has to ensure that a NPE is still thrown if the receiver object is null. By using the nullness analysis, we can avoid emitting this code in case the receiver object is known to be not-null. --- .../tools/nsc/backend/jvm/opt/CallGraph.scala | 26 +++++++++++++++------- .../scala/tools/nsc/backend/jvm/opt/Inliner.scala | 10 +++++---- test/files/neg/inlineMaxSize.check | 4 ++-- test/files/neg/inlineMaxSize.scala | 2 +- .../tools/nsc/backend/jvm/opt/InlinerTest.scala | 16 +++++++++++++ 5 files changed, 43 insertions(+), 15 deletions(-) (limited to 'test') 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..c6df86b297 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,14 @@ package backend.jvm package opt import scala.reflect.internal.util.{NoPosition, Position} +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 +95,13 @@ 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 = new NullnessAnalyzer + analyzer.analyze(definingClass.internalName, methodNode) methodNode.instructions.iterator.asScala.collect({ case call: MethodInsnNode => @@ -126,13 +129,20 @@ class CallGraph[BT <: BTypes](val btypes: BT) { Nil } + val receiverNotNull = call.getOpcode == Opcodes.INVOKESTATIC || { + val numArgs = Type.getArgumentTypes(call.desc).length + val frame = analyzer.frameAt(call, methodNode) + frame.getStack(frame.getStackSize - 1 - numArgs).nullness == NotNull + } + 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 +164,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 3aca15da69..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 @@ -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 @@ -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/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/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", "") } + + @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 + } } -- cgit v1.2.3 From 460e10cdb2fdfb9becaed5590ec77c7d5324a4db Mon Sep 17 00:00:00 2001 From: Lukas Rytz Date: Sun, 24 May 2015 14:05:24 +0200 Subject: Address review feedback Address feedback in #4516 / 57b8da4cd8. Save allocations of NullnessValue - there's only 4 possible instances. Also save tuple allocations in InstructionStackEffect. --- .../nsc/backend/jvm/analysis/AliasingFrame.scala | 8 +- .../jvm/analysis/InstructionStackEffect.scala | 104 ++++++++++++--------- .../backend/jvm/analysis/NullnessAnalyzer.scala | 48 +++++++--- .../jvm/analysis/NullnessAnalyzerTest.scala | 18 ++-- 4 files changed, 109 insertions(+), 69 deletions(-) (limited to 'test') diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala index 9494553ce1..7bbe1e2a49 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala @@ -38,7 +38,7 @@ class AliasingFrame[V <: Value](nLocals: Int, nStack: Int) extends Frame[V](nLoc /** * 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) + 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. @@ -71,7 +71,11 @@ class AliasingFrame[V <: Value](nLocals: Int, nStack: Int) extends Frame[V](nLoc 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 + // 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 { diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala index 56c8c2e4e3..a7d6f74557 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala @@ -8,8 +8,26 @@ 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 @@ -20,7 +38,7 @@ object InstructionStackEffect { (insn.getOpcode: @switch) match { // The order of opcodes is the same as in Frame.execute. - case NOP => (0, 0) + case NOP => t(0, 0) case ACONST_NULL | ICONST_M1 | @@ -44,7 +62,7 @@ object InstructionStackEffect { LLOAD | FLOAD | DLOAD | - ALOAD => (0, 1) + ALOAD => t(0, 1) case IALOAD | LALOAD | @@ -53,13 +71,13 @@ object InstructionStackEffect { AALOAD | BALOAD | CALOAD | - SALOAD => (2, 1) + SALOAD => t(2, 1) case ISTORE | LSTORE | FSTORE | DSTORE | - ASTORE => (1, 0) + ASTORE => t(1, 0) case IASTORE | LASTORE | @@ -68,41 +86,41 @@ object InstructionStackEffect { AASTORE | BASTORE | CASTORE | - SASTORE => (3, 0) + SASTORE => t(3, 0) - case POP => (1, 0) + case POP => t(1, 0) case POP2 => val isSize2 = peekStack(0).getSize == 2 - if (isSize2) (1, 0) else (2, 0) + if (isSize2) t(1, 0) else t(2, 0) - case DUP => (0, 1) + case DUP => t(0, 1) - case DUP_X1 => (2, 3) + case DUP_X1 => t(2, 3) case DUP_X2 => val isSize2 = peekStack(1).getSize == 2 - if (isSize2) (2, 3) else (3, 4) + if (isSize2) t(2, 3) else t(3, 4) case DUP2 => val isSize2 = peekStack(0).getSize == 2 - if (isSize2) (0, 1) else (0, 2) + if (isSize2) t(0, 1) else t(0, 2) case DUP2_X1 => val isSize2 = peekStack(0).getSize == 2 - if (isSize2) (2, 3) else (3, 4) + 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) (2, 3) else (3, 4) + if (v2isSize2) t(2, 3) else t(3, 4) } else { val v3isSize2 = peekStack(2).getSize == 2 - if (v3isSize2) (3, 5) else (4, 6) + if (v3isSize2) t(3, 5) else t(4, 6) } - case SWAP => (2, 2) + case SWAP => t(2, 2) case IADD | LADD | @@ -123,12 +141,12 @@ object InstructionStackEffect { IREM | LREM | FREM | - DREM => (2, 1) + DREM => t(2, 1) case INEG | LNEG | FNEG | - DNEG => (1, 1) + DNEG => t(1, 1) case ISHL | LSHL | @@ -141,9 +159,9 @@ object InstructionStackEffect { IOR | LOR | IXOR | - LXOR => (2, 1) + LXOR => t(2, 1) - case IINC => (0, 0) + case IINC => t(0, 0) case I2L | I2F | @@ -159,20 +177,20 @@ object InstructionStackEffect { D2F | I2B | I2C | - I2S => (1, 1) + I2S => t(1, 1) case LCMP | FCMPL | FCMPG | DCMPL | - DCMPG => (2, 1) + DCMPG => t(2, 1) case IFEQ | IFNE | IFLT | IFGE | IFGT | - IFLE => (1, 0) + IFLE => t(1, 0) case IF_ICMPEQ | IF_ICMPNE | @@ -181,32 +199,32 @@ object InstructionStackEffect { IF_ICMPGT | IF_ICMPLE | IF_ACMPEQ | - IF_ACMPNE => (2, 0) + IF_ACMPNE => t(2, 0) - case GOTO => (0, 0) + case GOTO => t(0, 0) - case JSR => (0, 1) + case JSR => t(0, 1) - case RET => (0, 0) + case RET => t(0, 0) case TABLESWITCH | - LOOKUPSWITCH => (1, 0) + LOOKUPSWITCH => t(1, 0) case IRETURN | LRETURN | FRETURN | DRETURN | - ARETURN => (1, 0) // Frame.execute consumes one stack value + ARETURN => t(1, 0) // Frame.execute consumes one stack value - case RETURN => (0, 0) // Frame.execute does not change the stack + case RETURN => t(0, 0) // Frame.execute does not change the stack - case GETSTATIC => (0, 1) + case GETSTATIC => t(0, 1) - case PUTSTATIC => (1, 0) + case PUTSTATIC => t(1, 0) - case GETFIELD => (1, 1) + case GETFIELD => t(1, 1) - case PUTFIELD => (2, 0) + case PUTFIELD => t(2, 0) case INVOKEVIRTUAL | INVOKESPECIAL | @@ -215,33 +233,33 @@ object InstructionStackEffect { 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) + 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 - (cons, prod) + t(cons, prod) - case NEW => (0, 1) + case NEW => t(0, 1) case NEWARRAY | ANEWARRAY | - ARRAYLENGTH => (1, 1) + ARRAYLENGTH => t(1, 1) - case ATHROW => (1, 0) // Frame.execute consumes one stack value + case ATHROW => t(1, 0) // Frame.execute consumes one stack value - case CHECKCAST => (0, 0) + case CHECKCAST => t(0, 0) - case INSTANCEOF => (1, 1) + case INSTANCEOF => t(1, 1) case MONITORENTER | - MONITOREXIT => (1, 0) + MONITOREXIT => t(1, 0) - case MULTIANEWARRAY => (insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1) + case MULTIANEWARRAY => t(insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1) case IFNULL | - IFNONNULL => (1, 0) + 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 index 18c17bc992..4c81b85d0a 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala @@ -100,25 +100,43 @@ 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) +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 (longOrDouble) 2 else 1 + def getSize: Int = if (isSize2) 2 else 1 - def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, longOrDouble) + 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, insn: AbstractInsnNode) = new NullnessValue(nullness, insn) + 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) { @@ -133,12 +151,12 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) // (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 ) + 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, longOrDouble = false) + if (isInstanceMethod && local == 0) NullnessValue(NotNull, isSize2 = false) else super.newParameterValue(isInstanceMethod, local, tp) } @@ -162,7 +180,7 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) def unaryOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = (insn.getOpcode: @switch) match { case Opcodes.NEWARRAY | - Opcodes.ANEWARRAY => NullnessValue(NotNull, longOrDouble = false) + Opcodes.ANEWARRAY => NullnessValue(NotNull, isSize2 = false) case _ => NullnessValue(Unknown, insn) } @@ -172,12 +190,12 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) } def ternaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue, value3: NullnessValue): NullnessValue = { - NullnessValue(Unknown, longOrDouble = false) + NullnessValue(Unknown, isSize2 = false) } def naryOperation(insn: AbstractInsnNode, values: util.List[_ <: NullnessValue]): NullnessValue = (insn.getOpcode: @switch) match { case Opcodes.MULTIANEWARRAY => - NullnessValue(NotNull, longOrDouble = false) + NullnessValue(NotNull, isSize2 = false) case _ => // TODO: use a list of methods that are known to return non-null values @@ -247,7 +265,7 @@ class NullnessFrame(nLocals: Int, nStack: Int) extends AliasingFrame[NullnessVal if (nullCheckedAliasId != -1) { for (i <- valuesWithAliasId(nullCheckedAliasId)) - this.setValue(i, this.getValue(i).copy(nullness = NotNull)) + this.setValue(i, NotNullValue) } } } diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala index 92574329db..3d5343e395 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala @@ -63,9 +63,9 @@ class NullnessAnalyzerTest extends ClearAfterClass { 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"))) + 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(", ") } @@ -82,13 +82,13 @@ class NullnessAnalyzerTest extends ClearAfterClass { // 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: 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 - assertTrue(showAllNullnessFrames(newNullnessAnalyzer(m), m) == res) + assertEquals(showAllNullnessFrames(newNullnessAnalyzer(m), m), res) } @Test -- cgit v1.2.3 From b2a78b3ab536658f79e4396201c730a8408d3dd2 Mon Sep 17 00:00:00 2001 From: Lukas Rytz Date: Wed, 3 Jun 2015 22:46:00 +0200 Subject: Fix aliasing / nullness of CHECKCAST --- .../jvm/analysis/InstructionStackEffect.scala | 5 ++--- .../backend/jvm/analysis/NullnessAnalyzer.scala | 2 ++ .../jvm/analysis/NullnessAnalyzerTest.scala | 26 ++++++++++++++++++++++ 3 files changed, 30 insertions(+), 3 deletions(-) (limited to 'test') diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala index a7d6f74557..98e93c125b 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala @@ -249,9 +249,8 @@ object InstructionStackEffect { case ATHROW => t(1, 0) // Frame.execute consumes one stack value - case CHECKCAST => t(0, 0) - - case INSTANCEOF => t(1, 1) + case CHECKCAST | + INSTANCEOF => t(1, 1) // Frame.execute does push(pop()) for both of them case MONITORENTER | MONITOREXIT => 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 index 2cc6d67a3c..31710dcbee 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala @@ -179,6 +179,8 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) 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) diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala index 3d5343e395..3a85f03da2 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala @@ -202,4 +202,30 @@ class NullnessAnalyzerTest extends ClearAfterClass { (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) + } } -- cgit v1.2.3