diff options
author | Lukas Rytz <lukas.rytz@gmail.com> | 2016-02-12 14:04:44 +0100 |
---|---|---|
committer | Lukas Rytz <lukas.rytz@gmail.com> | 2016-02-13 17:04:21 +0100 |
commit | f70c77e1c4d5b6c951669d79cf73a1ff0b932312 (patch) | |
tree | 02c0f226445a2e0002bbfb472ad9f337b02e5c3f | |
parent | 7c25282ff91445dc1bdc20e49b68c2d20c318876 (diff) | |
download | scala-f70c77e1c4d5b6c951669d79cf73a1ff0b932312.tar.gz scala-f70c77e1c4d5b6c951669d79cf73a1ff0b932312.tar.bz2 scala-f70c77e1c4d5b6c951669d79cf73a1ff0b932312.zip |
Generate leaner code for branches
GenBCode used to generate more bytecode for branching instructions than
GenASM. A simple method
def f(x: Int, b: Boolean) = if (b) 1 else 2
would generate
ILOAD 2
IFNE L1
GOTO L2
L1
ICONST_1
GOTO L3
L2
ICONST_2
L3
IRETURN
If the conditional branch is negated (IFEQ) the GOTO is unnecessary.
While -Yopt:l:method would clean this up, it's also not too hard to
generate the leaner bytecode in the first place.
3 files changed, 173 insertions, 91 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala index a28d4b0083..1e7ea0c09d 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala @@ -202,14 +202,14 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { val hasElse = !elsep.isEmpty val postIf = if (hasElse) new asm.Label else failure - genCond(condp, success, failure) + genCond(condp, success, failure, targetIfNoJump = success) + markProgramPoint(success) val thenKind = tpeTK(thenp) val elseKind = if (!hasElse) UNIT else tpeTK(elsep) def hasUnitBranch = (thenKind == UNIT || elseKind == UNIT) val resKind = if (hasUnitBranch) UNIT else tpeTK(tree) - markProgramPoint(success) genLoad(thenp, resKind) if (hasElse) { bc goTo postIf } markProgramPoint(failure) @@ -234,14 +234,14 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { else if (isArrayOp(code)) genArrayOp(tree, code, expectedType) else if (isLogicalOp(code) || isComparisonOp(code)) { val success, failure, after = new asm.Label - genCond(tree, success, failure) + genCond(tree, success, failure, targetIfNoJump = success) // success block - markProgramPoint(success) - bc boolconst true - bc goTo after + markProgramPoint(success) + bc boolconst true + bc goTo after // failure block - markProgramPoint(failure) - bc boolconst false + markProgramPoint(failure) + bc boolconst false // after markProgramPoint(after) @@ -1108,53 +1108,58 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { } /* Emit code to compare the two top-most stack values using the 'op' operator. */ - private def genCJUMP(success: asm.Label, failure: asm.Label, op: TestOp, tk: BType) { - if (tk.isIntSizedType) { // BOOL, BYTE, CHAR, SHORT, or INT - bc.emitIF_ICMP(op, success) - } else if (tk.isRef) { // REFERENCE(_) | ARRAY(_) - bc.emitIF_ACMP(op, success) - } else { - (tk: @unchecked) match { - case LONG => emit(asm.Opcodes.LCMP) - case FLOAT => - if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.FCMPG) - else emit(asm.Opcodes.FCMPL) - case DOUBLE => - if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.DCMPG) - else emit(asm.Opcodes.DCMPL) + private def genCJUMP(success: asm.Label, failure: asm.Label, op: TestOp, tk: BType, targetIfNoJump: asm.Label) { + if (targetIfNoJump == success) genCJUMP(failure, success, op.negate, tk, targetIfNoJump) + else { + if (tk.isIntSizedType) { // BOOL, BYTE, CHAR, SHORT, or INT + bc.emitIF_ICMP(op, success) + } else if (tk.isRef) { // REFERENCE(_) | ARRAY(_) + bc.emitIF_ACMP(op, success) + } else { + (tk: @unchecked) match { + case LONG => emit(asm.Opcodes.LCMP) + case FLOAT => + if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.FCMPG) + else emit(asm.Opcodes.FCMPL) + case DOUBLE => + if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.DCMPG) + else emit(asm.Opcodes.DCMPL) + } + bc.emitIF(op, success) } - bc.emitIF(op, success) + if (targetIfNoJump != failure) bc goTo failure } - bc goTo failure } /* Emits code to compare (and consume) stack-top and zero using the 'op' operator */ - private def genCZJUMP(success: asm.Label, failure: asm.Label, op: TestOp, tk: BType) { - if (tk.isIntSizedType) { // BOOL, BYTE, CHAR, SHORT, or INT - bc.emitIF(op, success) - } else if (tk.isRef) { // REFERENCE(_) | ARRAY(_) - // @unchecked because references aren't compared with GT, GE, LT, LE. - (op : @unchecked) match { - case TestOp.EQ => bc emitIFNULL success - case TestOp.NE => bc emitIFNONNULL success - } - } else { - (tk: @unchecked) match { - case LONG => - emit(asm.Opcodes.LCONST_0) - emit(asm.Opcodes.LCMP) - case FLOAT => - emit(asm.Opcodes.FCONST_0) - if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.FCMPG) - else emit(asm.Opcodes.FCMPL) - case DOUBLE => - emit(asm.Opcodes.DCONST_0) - if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.DCMPG) - else emit(asm.Opcodes.DCMPL) + private def genCZJUMP(success: asm.Label, failure: asm.Label, op: TestOp, tk: BType, targetIfNoJump: asm.Label) { + if (targetIfNoJump == success) genCZJUMP(failure, success, op.negate, tk, targetIfNoJump) + else { + if (tk.isIntSizedType) { // BOOL, BYTE, CHAR, SHORT, or INT + bc.emitIF(op, success) + } else if (tk.isRef) { // REFERENCE(_) | ARRAY(_) + op match { // references are only compared with EQ and NE + case TestOp.EQ => bc emitIFNULL success + case TestOp.NE => bc emitIFNONNULL success + } + } else { + (tk: @unchecked) match { + case LONG => + emit(asm.Opcodes.LCONST_0) + emit(asm.Opcodes.LCMP) + case FLOAT => + emit(asm.Opcodes.FCONST_0) + if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.FCMPG) + else emit(asm.Opcodes.FCMPL) + case DOUBLE => + emit(asm.Opcodes.DCONST_0) + if (op == TestOp.LT || op == TestOp.LE) emit(asm.Opcodes.DCMPG) + else emit(asm.Opcodes.DCMPL) + } + bc.emitIF(op, success) } - bc.emitIF(op, success) + if (targetIfNoJump != failure) bc goTo failure } - bc goTo failure } def testOpForPrimitive(primitiveCode: Int) = (primitiveCode: @switch) match { @@ -1179,29 +1184,26 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { * Generate code for conditional expressions. * The jump targets success/failure of the test are `then-target` and `else-target` resp. */ - private def genCond(tree: Tree, success: asm.Label, failure: asm.Label) { + private def genCond(tree: Tree, success: asm.Label, failure: asm.Label, targetIfNoJump: asm.Label) { def genComparisonOp(l: Tree, r: Tree, code: Int) { - val op: TestOp = testOpForPrimitive(code) - // special-case reference (in)equality test for null (null eq x, x eq null) - var nonNullSide: Tree = null - if (scalaPrimitives.isReferenceEqualityOp(code) && - { nonNullSide = ifOneIsNull(l, r); nonNullSide != null } - ) { + val op = testOpForPrimitive(code) + val nonNullSide = if (scalaPrimitives.isReferenceEqualityOp(code)) ifOneIsNull(l, r) else null + if (nonNullSide != null) { + // special-case reference (in)equality test for null (null eq x, x eq null) genLoad(nonNullSide, ObjectRef) - genCZJUMP(success, failure, op, ObjectRef) - } - else { + genCZJUMP(success, failure, op, ObjectRef, targetIfNoJump) + } else { val tk = tpeTK(l).maxType(tpeTK(r)) genLoad(l, tk) genLoad(r, tk) - genCJUMP(success, failure, op, tk) + genCJUMP(success, failure, op, tk, targetIfNoJump) } } - def default() = { + def loadAndTestBoolean() = { genLoad(tree, BOOL) - genCZJUMP(success, failure, TestOp.NE, BOOL) + genCZJUMP(success, failure, TestOp.NE, BOOL, targetIfNoJump) } lineNumber(tree) @@ -1212,37 +1214,35 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { // lhs and rhs of test lazy val Select(lhs, _) = fun - val rhs = if (args.isEmpty) EmptyTree else args.head; // args.isEmpty only for ZNOT + val rhs = if (args.isEmpty) EmptyTree else args.head // args.isEmpty only for ZNOT - def genZandOrZor(and: Boolean) { // TODO WRONG + def genZandOrZor(and: Boolean) { // reaching "keepGoing" indicates the rhs should be evaluated too (ie not short-circuited). val keepGoing = new asm.Label - if (and) genCond(lhs, keepGoing, failure) - else genCond(lhs, success, keepGoing) + if (and) genCond(lhs, keepGoing, failure, targetIfNoJump = keepGoing) + else genCond(lhs, success, keepGoing, targetIfNoJump = keepGoing) markProgramPoint(keepGoing) - genCond(rhs, success, failure) + genCond(rhs, success, failure, targetIfNoJump) } getPrimitive(fun.symbol) match { - case ZNOT => genCond(lhs, failure, success) + case ZNOT => genCond(lhs, failure, success, targetIfNoJump) case ZAND => genZandOrZor(and = true) case ZOR => genZandOrZor(and = false) case code => - // TODO !!!!!!!!!! isReferenceType, in the sense of TypeKind? (ie non-array, non-boxed, non-nothing, may be null) if (scalaPrimitives.isUniversalEqualityOp(code) && tpeTK(lhs).isClass) { - // `lhs` has reference type - if (code == EQ) genEqEqPrimitive(lhs, rhs, success, failure, tree.pos) - else genEqEqPrimitive(lhs, rhs, failure, success, tree.pos) - } - else if (scalaPrimitives.isComparisonOp(code)) + // rewrite `==` to null tests and `equals`. not needed for arrays (`equals` is reference equality). + if (code == EQ) genEqEqPrimitive(lhs, rhs, success, failure, targetIfNoJump, tree.pos) + else genEqEqPrimitive(lhs, rhs, failure, success, targetIfNoJump, tree.pos) + } else if (scalaPrimitives.isComparisonOp(code)) { genComparisonOp(lhs, rhs, code) - else - default + } else + loadAndTestBoolean() } - case _ => default + case _ => loadAndTestBoolean() } } // end of genCond() @@ -1254,7 +1254,7 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { * @param l left-hand-side of the '==' * @param r right-hand-side of the '==' */ - def genEqEqPrimitive(l: Tree, r: Tree, success: asm.Label, failure: asm.Label, pos: Position) { + def genEqEqPrimitive(l: Tree, r: Tree, success: asm.Label, failure: asm.Label, targetIfNoJump: asm.Label, pos: Position) { /* True if the equality comparison is between values that require the use of the rich equality * comparator (scala.runtime.Comparator.equals). This is the case when either side of the @@ -1264,7 +1264,6 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { */ val mustUseAnyComparator: Boolean = { val areSameFinals = l.tpe.isFinalType && r.tpe.isFinalType && (l.tpe =:= r.tpe) - !areSameFinals && platform.isMaybeBoxed(l.tpe.typeSymbol) && platform.isMaybeBoxed(r.tpe.typeSymbol) } @@ -1279,23 +1278,22 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { genLoad(l, ObjectRef) genLoad(r, ObjectRef) genCallMethod(equalsMethod, InvokeStyle.Static, pos) - genCZJUMP(success, failure, TestOp.NE, BOOL) - } - else { + genCZJUMP(success, failure, TestOp.NE, BOOL, targetIfNoJump) + } else { if (isNull(l)) { // null == expr -> expr eq null genLoad(r, ObjectRef) - genCZJUMP(success, failure, TestOp.EQ, ObjectRef) + genCZJUMP(success, failure, TestOp.EQ, ObjectRef, targetIfNoJump) } else if (isNull(r)) { // expr == null -> expr eq null genLoad(l, ObjectRef) - genCZJUMP(success, failure, TestOp.EQ, ObjectRef) + genCZJUMP(success, failure, TestOp.EQ, ObjectRef, targetIfNoJump) } else if (isNonNullExpr(l)) { // SI-7852 Avoid null check if L is statically non-null. genLoad(l, ObjectRef) genLoad(r, ObjectRef) genCallMethod(Object_equals, InvokeStyle.Virtual, pos) - genCZJUMP(success, failure, TestOp.NE, BOOL) + genCZJUMP(success, failure, TestOp.NE, BOOL, targetIfNoJump) } else { // l == r -> if (l eq null) r eq null else l.equals(r) val eqEqTempLocal = locals.makeLocal(ObjectRef, nme.EQEQ_LOCAL_VAR.toString) @@ -1306,17 +1304,17 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { genLoad(r, ObjectRef) locals.store(eqEqTempLocal) bc dup ObjectRef - genCZJUMP(lNull, lNonNull, TestOp.EQ, ObjectRef) + genCZJUMP(lNull, lNonNull, TestOp.EQ, ObjectRef, targetIfNoJump = lNull) markProgramPoint(lNull) bc drop ObjectRef locals.load(eqEqTempLocal) - genCZJUMP(success, failure, TestOp.EQ, ObjectRef) + genCZJUMP(success, failure, TestOp.EQ, ObjectRef, targetIfNoJump = lNonNull) markProgramPoint(lNonNull) locals.load(eqEqTempLocal) genCallMethod(Object_equals, InvokeStyle.Virtual, pos) - genCZJUMP(success, failure, TestOp.NE, BOOL) + genCZJUMP(success, failure, TestOp.NE, BOOL, targetIfNoJump) } } } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala index 1b5ece772c..f423f3c7fe 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala @@ -1355,6 +1355,15 @@ object BCodeHelpers { } class TestOp(val op: Int) extends AnyVal { + import TestOp._ + def negate = this match { + case EQ => NE + case NE => EQ + case LT => GE + case GE => LT + case GT => LE + case LE => GT + } def opcodeIF = asm.Opcodes.IFEQ + op def opcodeIFICMP = asm.Opcodes.IF_ICMPEQ + op } diff --git a/test/junit/scala/issues/BytecodeTest.scala b/test/junit/scala/issues/BytecodeTest.scala index 7260f43c87..ca1b33ed20 100644 --- a/test/junit/scala/issues/BytecodeTest.scala +++ b/test/junit/scala/issues/BytecodeTest.scala @@ -3,7 +3,7 @@ package scala.issues import org.junit.runner.RunWith import org.junit.runners.JUnit4 import org.junit.Test -import scala.tools.asm.Opcodes +import scala.tools.asm.Opcodes._ import scala.tools.nsc.backend.jvm.AsmUtils import scala.tools.nsc.backend.jvm.CodeGenTools._ import org.junit.Assert._ @@ -105,12 +105,10 @@ class BytecodeTest extends ClearAfterClass { val unapplyLineNumbers = getSingleMethod(module, "unapply").instructions.filter(_.isInstanceOf[LineNumber]) assert(unapplyLineNumbers == List(LineNumber(2, Label(0))), unapplyLineNumbers) - import Opcodes._ val expected = List( LineNumber(4, Label(0)), LineNumber(5, Label(5)), - Jump(IFNE, Label(11)), - Jump(GOTO, Label(20)), + Jump(IFEQ, Label(20)), LineNumber(6, Label(11)), Invoke(INVOKEVIRTUAL, "scala/Predef$", "println", "(Ljava/lang/Object;)V", false), @@ -133,4 +131,81 @@ class BytecodeTest extends ClearAfterClass { } assertSameCode(mainIns, expected) } + + @Test + def bytecodeForBranches(): Unit = { + val code = + """class C { + | def t1(b: Boolean) = if (b) 1 else 2 + | def t2(x: Int) = if (x == 393) 1 else 2 + | def t3(a: Array[String], b: AnyRef) = a != b && b == a + | def t4(a: AnyRef) = a == null || null != a + | def t5(a: AnyRef) = (a eq null) || (null ne a) + | def t6(a: Int, b: Boolean) = if ((a == 10) && b || a != 1) 1 else 2 + | def t7(a: AnyRef, b: AnyRef) = a == b + | def t8(a: AnyRef) = Nil == a || "" != a + |} + """.stripMargin + + val List(c) = compileClasses(compiler)(code) + + // t1: no unnecessary GOTOs + assertSameCode(getSingleMethod(c, "t1").instructions.dropNonOp, List( + VarOp(ILOAD, 1), Jump(IFEQ, Label(6)), + Op(ICONST_1), Jump(GOTO, Label(9)), + Label(6), Op(ICONST_2), + Label(9), Op(IRETURN))) + + // t2: no unnecessary GOTOs + assertSameCode(getSingleMethod(c, "t2").instructions.dropNonOp, List( + VarOp(ILOAD, 1), IntOp(SIPUSH, 393), Jump(IF_ICMPNE, Label(7)), + Op(ICONST_1), Jump(GOTO, Label(10)), + Label(7), Op(ICONST_2), + Label(10), Op(IRETURN))) + + // t3: Array == is translated to reference equality, AnyRef == to null checks and equals + assertSameCode(getSingleMethod(c, "t3").instructions.dropNonOp, List( + // Array == + VarOp(ALOAD, 1), VarOp(ALOAD, 2), Jump(IF_ACMPEQ, Label(23)), + // AnyRef == + VarOp(ALOAD, 2), VarOp(ALOAD, 1), VarOp(ASTORE, 3), Op(DUP), Jump(IFNONNULL, Label(14)), + Op(POP), VarOp(ALOAD, 3), Jump(IFNULL, Label(19)), Jump(GOTO, Label(23)), + Label(14), VarOp(ALOAD, 3), Invoke(INVOKEVIRTUAL, "java/lang/Object", "equals", "(Ljava/lang/Object;)Z", false), Jump(IFEQ, Label(23)), + Label(19), Op(ICONST_1), Jump(GOTO, Label(26)), + Label(23), Op(ICONST_0), + Label(26), Op(IRETURN))) + + val t4t5 = List( + VarOp(ALOAD, 1), Jump(IFNULL, Label(6)), + VarOp(ALOAD, 1), Jump(IFNULL, Label(10)), + Label(6), Op(ICONST_1), Jump(GOTO, Label(13)), + Label(10), Op(ICONST_0), + Label(13), Op(IRETURN)) + + // t4: one side is known null, so just a null check on the other + assertSameCode(getSingleMethod(c, "t4").instructions.dropNonOp, t4t5) + + // t5: one side known null, so just a null check on the other + assertSameCode(getSingleMethod(c, "t5").instructions.dropNonOp, t4t5) + + // t6: no unnecessary GOTOs + assertSameCode(getSingleMethod(c, "t6").instructions.dropNonOp, List( + VarOp(ILOAD, 1), IntOp(BIPUSH, 10), Jump(IF_ICMPNE, Label(7)), + VarOp(ILOAD, 2), Jump(IFNE, Label(12)), + Label(7), VarOp(ILOAD, 1), Op(ICONST_1), Jump(IF_ICMPEQ, Label(16)), + Label(12), Op(ICONST_1), Jump(GOTO, Label(19)), + Label(16), Op(ICONST_2), + Label(19), Op(IRETURN))) + + // t7: universal equality + assertInvoke(getSingleMethod(c, "t7"), "scala/runtime/BoxesRunTime", "equals") + + // t8: no null checks invoking equals on modules and constants + assertSameCode(getSingleMethod(c, "t8").instructions.dropNonOp, List( + Field(GETSTATIC, "scala/collection/immutable/Nil$", "MODULE$", "Lscala/collection/immutable/Nil$;"), VarOp(ALOAD, 1), Invoke(INVOKEVIRTUAL, "java/lang/Object", "equals", "(Ljava/lang/Object;)Z", false), Jump(IFNE, Label(10)), + Ldc(LDC, ""), VarOp(ALOAD, 1), Invoke(INVOKEVIRTUAL, "java/lang/Object", "equals", "(Ljava/lang/Object;)Z", false), Jump(IFNE, Label(14)), + Label(10), Op(ICONST_1), Jump(GOTO, Label(17)), + Label(14), Op(ICONST_0), + Label(17), Op(IRETURN))) + } } |