New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

generate correct bytecode for switch in argument #5672

Closed
scabug opened this Issue Apr 14, 2012 · 15 comments

Comments

Projects
None yet
1 participant
@scabug
Copy link

scabug commented Apr 14, 2012

the optimizer generates broken bytecode for 'println(1 match { case x => x})'

compiler built from scala/scala@4804efe or later (virtpatmat on by default)

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Apr 14, 2012

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Apr 14, 2012

@adriaanm said:
test file:

 class Test {
   def broken = println(1 match { case x => x})
 }

bytecode:

scala> :javap -v Test
Compiled from "t5672.scala"
....
{
public void broken();
  Code:
   Stack=2, Locals=1, Args_size=1
   0:	iconst_1
   1:	iconst_1
   2:	invokestatic	#12; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   5:	invokevirtual	#18; //Method scala/Predef$.println:(Ljava/lang/Object;)V
   8:	return
  LineNumberTable: 
   line 2: 0

.... 

ASM analysis of the bytecode:

[adriaan@Adriaans-Mac-mini scala (topic/virtpatmat *$=)]$ qs -cp ~/Dropbox/bin/asm/
Welcome to Scala version 2.10.0-20120414-115105-57c7debd62 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_31).
Type in expressions to have them evaluated.
Type :help for more information.

scala> org.objectweb.asm.util.CheckClassAdapter.main(Array("Test.class"))
org.objectweb.asm.tree.analysis.AnalyzerException: Error at instruction 3: Method owner: expected Lscala/Predef$;, but found I
	at org.objectweb.asm.tree.analysis.Analyzer.analyze(Unknown Source)
	at org.objectweb.asm.util.CheckClassAdapter.verify(Unknown Source)
	at org.objectweb.asm.util.CheckClassAdapter.verify(Unknown Source)
	at org.objectweb.asm.util.CheckClassAdapter.main(Unknown Source)
	at $line6.$read$$iw$$iw$.<init>(<console>:8)
	at $line6.$read$$iw$$iw$.<clinit>(<console>)
	at $line6.$eval$.<init>(<console>:7)
	at $line6.$eval$.<clinit>(<console>)
	at $line6.$eval.$print(<console>)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
	at java.lang.reflect.Method.invoke(Method.java:597)
	at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:767)
	at scala.tools.nsc.interpreter.IMain$Request$$anonfun$16.apply(IMain.scala:1018)
	at scala.tools.nsc.interpreter.Line.scala$tools$nsc$interpreter$Line$$runAndSetState(Line.scala:41)
	at scala.tools.nsc.interpreter.Line$$anonfun$2.apply$mcV$sp(Line.scala:47)
	at scala.tools.nsc.io.package$$anon$2.run(package.scala:22)
	at java.lang.Thread.run(Thread.java:680)
Caused by: org.objectweb.asm.tree.analysis.AnalyzerException: Method owner: expected Lscala/Predef$;, but found I
	at org.objectweb.asm.tree.analysis.BasicVerifier.naryOperation(Unknown Source)
	at org.objectweb.asm.tree.analysis.BasicVerifier.naryOperation(Unknown Source)
	at org.objectweb.asm.tree.analysis.Frame.execute(Unknown Source)
	... 19 more
broken()V
00000 LTest;  :  :     ICONST_1
00001 LTest;  : I  :     ICONST_1
00002 LTest;  : I I  :     INVOKESTATIC scala/runtime/BoxesRunTime.boxToInteger (I)Ljava/lang/Integer;
00003 LTest;  : I Integer  :     INVOKEVIRTUAL scala/Predef$.println (Ljava/lang/Object;)V
00004 ?    :     RETURN
@scabug

This comment has been minimized.

Copy link
Author

scabug commented Apr 14, 2012

@adriaanm said:
I don't think this is directly related to virtpatmat, since it simply emits a switch.
The difference with oldpatmat is that switches as simple as this were never emitted before.
I'll implement this simplification, but the inliner/optimizer should still be fixed.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Apr 15, 2012

@VladUreche said:
Miguel, since this is ASM-related, can you please have a look?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@magarciaEPFL said:
With or without optimize, it works as of scala/scala@6296e32

Anyway background follows.

-Xprint:cleanup shows the println argument is a Block consisting of a ValDef and two LabelDef:

    def broken(): Unit = scala.this.Predef.println({
      case <synthetic> val x1: Int = 1;
      case3(){
        matchEnd2(scala.Int.box(x1))
      };
      matchEnd2(x: Object){
        x
      }
    });

The "case" labels above are due to LabelDef (there are no CaseDef around)

  Block( // tree.tpe=Object
    // 2 statements
    ValDef( // case val x1: Int
      case <synthetic> <triedcooking>
      "x1"
      <tpt> // tree.tpe=Int
      1
    )
    LabelDef( // case def case3(): Object, tree.tpe=Object
      ()
      Apply( // case def matchEnd2(x: Object): Object, tree.tpe=Object
        "matchEnd2" // case def matchEnd2(x: Object): Object, tree.tpe=(x: Object)Object
        Apply( // def box(x: Int): Integer in object Int, tree.tpe=Object
          "scala"."Int"."box" // def box(x: Int): Integer in object Int, tree.tpe=(x: Int)Integer
          "x1" // case val x1: Int, tree.tpe=Int
        )
      )
    )
    LabelDef( // case def matchEnd2(x: Object): Object, tree.tpe=Object
      "x" // x: Object, tree.tpe=Object
      "x" // x: Object, tree.tpe=Object
    )
  )

After GenICode, the argument travels twice between stack and locals:

  // methods
  def broken(): Unit {
  locals: value x1, value x
  startBlock: 1
  blocks: [1,2,3]
  
  1: 
    3	LOAD_MODULE object Predef
    3	CONSTANT(1)
    3	STORE_LOCAL(value x1)
    3	SCOPE_ENTER value x1
    3	JUMP 2
    
  2: 
    3	LOAD_LOCAL(value x1)
    3	BOX INT
    3	STORE_LOCAL(value x)
    3	JUMP 3
    
  3: 
    3	LOAD_LOCAL(value x)
    3	SCOPE_EXIT value x1
    3	CALL_METHOD scala.Predef.println (dynamic)
    3	RETURN(UNIT)
    
  }

Actually -optimize manages to unclutter that:

public void broken();
  Code:
   Stack=2, Locals=1, Args_size=1
   0:   getstatic       #20; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   3:   iconst_1
   4:   invokestatic    #27; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   7:   invokevirtual   #31; //Method scala/Predef$.println:(Ljava/lang/Object;)V
   10:  return
  LineNumberTable:
   line 3: 0

Reaching definitions does most of the simplification (try with -Yclosure-elim -Ydead-code) but that leaves us with a

astore_1
aload_1

that PeepholeOpt can reduce only after IMethod.normalize() has run, and it's only Inliner that calls IMethod.normalize(). Therefore, we'll have to keep an eye on choppy BasicBlock (peephole optimizations don't straddle BasicBlock boundaries). Related: collapseJumpOnlyBlocks in GenASM.

There's no optimizer nor backend bug going on here. Any comments, before I close it as "Not-a-Bug" ?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@VladUreche said:
Afaik, Adriaan worked around this in c2cd6acf99. Did you revert that before trying it out?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@magarciaEPFL said:
@VladUreche, with c2cd6acf99 reverted, do you remember in which phase of the optimizer this bug shows up ?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@VladUreche said:
Nope, sorry, all I knew about was the workaround. Could it be related to inlineEH?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@VladUreche said:
See also 1a6e7129da.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@magarciaEPFL said:
Performance-wise, it's better to keep as straight-line code what can be formulated that way. You know, if two basic blocks:

  • are back to back, and
  • the former jumps to the second, and
  • no other block jumps to the second, and
  • no exception handler covers one but not the other,

then it's better to keep them as a single basic block.

I don't know what to make of "avoiding emitting tiny switches". In the example, a "tiny switch" isn't being emitted anymore, yet there are two intervening jumps. Reverting c2cd6acf99 would mean we get even more jumps, right? Doesn't seem like a good idea.

Any more comments?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@VladUreche said:
Wouldn't it make sense to diagnose the problem and fix it in case it also affects other code patterns?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@magarciaEPFL said:
Here's the tiny switch as of -Xprint:cleanup . Besides loading the scrutinee's value onto the stack, it consists of just the default case:

    def broken(): Unit = scala.this.Predef.println({
      case <synthetic> val x1: Int = 1;
      (x1: Int) match {
        case _ => scala.Int.box(x1)
      }
    });

In more detail ( -Yshow-trees ) the argument to println looks like:

  Block( // tree.tpe=Object
    ValDef( // case val x1: Int
      case <synthetic> <triedcooking>
      "x1"
      <tpt> // tree.tpe=Int
      1
    )
    Match( // tree.tpe=Object
      Typed( // tree.tpe=Int
        "x1" // case val x1: Int, tree.tpe=Int
        <tpt> // tree.tpe=Int
      )
      CaseDef( // tree.tpe=Object
        "_" // tree.tpe=Int
        Apply( // def box(x: Int): Integer in object Int, tree.tpe=Object
          "scala"."Int"."box" // def box(x: Int): Integer in object Int, tree.tpe=(x: Int)Integer
          "x1" // case val x1: Int, tree.tpe=Int
        )
      )
    )
  )

The VerifyError manifests only with -Yinline , although nothing gets inlined (confirm with -Ylog:inline ). Instead, malformed code emerges from IMethod.normalize() . Here's before:

  def broken(): Unit {
  locals: value x1
  startBlock: 1
  blocks: [1,2,3]
  
  1: 
    3	LOAD_MODULE object Predef
    3	CONSTANT(1)
    3	STORE_LOCAL(value x1)
    3	SCOPE_ENTER value x1
    3	LOAD_LOCAL(value x1)
    3	SWITCH ...
    
  3: 
    3	LOAD_LOCAL(value x1)
    3	BOX INT
    3	JUMP 2
    
  2: 
    3	CALL_METHOD scala.Predef.println (dynamic)
    3	RETURN(UNIT)
    
  }

And here's after. There's a LOAD_LOCAL too many, because the SWITCH instruction was simply elided as if it were an unconditional jump and the scrutinee was left on the stack.

  // methods
  def broken(): Unit {
  locals: value x1
  startBlock: 1
  blocks: [1]
  
  1: 
    3	LOAD_MODULE object Predef
    3	CONSTANT(1)
    3	STORE_LOCAL(value x1)
    3	SCOPE_ENTER value x1
    3	LOAD_LOCAL(value x1)
    3	LOAD_LOCAL(value x1)
    3	BOX INT
    3	CALL_METHOD scala.Predef.println (dynamic)
    3	RETURN(UNIT)
    
  }

An assertion in IMethod.normalize() would have saved the day: bb.removeLastInstruction works under the assumption that bb.lastInstruction.isInstanceOf[JUMP] . The following covers corner cases:

    val lastInstr = bb.lastInstruction
    /* Ticket SI-5672
     * Besides removing the control-flow instruction at the end of `bb` (usually a JUMP), we have to pop any values it pushes.
     * Examples:
     *   `SWITCH` consisting of just the default case, or
     *   `CJUMP(targetBlock, targetBlock, _, _)` ie where success and failure targets coincide (consumes two stack values).
     */
    val oldTKs = lastInstr.consumedTypes
    assert(lastInstr.consumed == oldTKs.size, "Someone forgot to override consumedTypes() in " +  lastInstr)

      bb.removeLastInstruction
      for(tk <- oldTKs.reverse) { bb.emit(DROP(tk), lastInstr.pos) }
      succ.toList foreach { i => bb.emit(i, i.pos) }
      code.removeBlock(succ)
      exh foreach { e => e.covered = e.covered - succ }

    nextBlock -= bb

The end result after -optimize is clutter free:

public void broken();
  Code:
   Stack=2, Locals=1, Args_size=1
   0:   getstatic       #20; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   3:   iconst_1
   4:   invokestatic    #27; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   7:   invokevirtual   #31; //Method scala/Predef$.println:(Ljava/lang/Object;)V
   10:  return
@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 21, 2012

@VladUreche said:
Great work Miguel! Thanks a lot for looking into this!

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 22, 2012

@magarciaEPFL said:
Pull request with fix at scala/scala#596

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 23, 2012

@magarciaEPFL said:
Fixed in 3eb0245cd

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment