Skip to content
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

Jump to bottom

Conditional optimization: true || x == true, false && y == false, etc. #6105

Open
scabug opened this issue Jul 18, 2012 · 11 comments
Open

Conditional optimization: true || x == true, false && y == false, etc. #6105

scabug opened this issue Jul 18, 2012 · 11 comments
Labels
enhancement optimizer
Milestone
Backlog

Comments

@scabug
Copy link

scabug commented Jul 18, 2012

There are four key optimizations that Mondrian's optimizer could make but doesn't.

Mondrian's optimizer is smart enough to turn if (true) a else b into a. To my delight, it is smart enough to do this even if true is inside a final val and not the literal true. This zeroth-order optimization is very helpful.

However, Mondrian's optimizer misses several key first-order optimizations that are quite useful.

  • true || x == true
  • false && y == false
  • true && x == x
  • false || y == y
  • x && true == x
  • y || false == y

Unfortunately, you have to be careful with the two remaining cases unless you can prove that x & y are side-effect free.

  • x || true == {x; true}
  • y && false == {y; false}

This is something that is pretty easy to encounter in performance-critical cases where you don't really want to have to rely on the JIT optimizer to be smart enough.

  class {
    final val extremeLogs = false
    for (tightLoop) {
      if (extremeLogs && logger.isTraceEnabled) { ... }
      ...
    }
  }

One would hope that the optimizer would actually be smart enough to recurse through boolean expressions and apply these transformations from the outside in. There are also some additional safe transformations like x && true && y == x && y.
@scabug
Copy link
Author

scabug commented Jul 18, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6105?orig=1
Reporter: Sarah Gerweck (gerweck)
Affected Versions: 2.9.2

@scabug
Copy link
Author

scabug commented Jul 31, 2012

@magarciaEPFL said:
I'll think about it.

@scabug
Copy link
Author

scabug commented Oct 25, 2012

@magarciaEPFL said:
This is supported by the experimental optimizer that eventually will replace the current one.

Description: https://groups.google.com/d/topic/scala-internals/iz5PiIMTPs0/discussion

Sources at branch: https://github.com/magarciaEPFL/scala/tree/GenBCodeOpt

@SethTisue
Copy link
Member

@lrytz did this happen?

@lrytz
Copy link
Member

lrytz commented Mar 7, 2018

works in 2.12

@lrytz lrytz closed this as completed Mar 7, 2018
@lrytz
Copy link
Member

lrytz commented Mar 7, 2018 •
edited

(i didn't intend to close, was on the wrong ticket)

these are not yet implemented

  • true && x ==> x
  • false || y ==> y
  • x && true ==> x
  • y || false ==> y

@lrytz lrytz reopened this Mar 7, 2018
@NthPortal
Copy link

NthPortal commented Mar 7, 2018 •
edited

the first two are not necessarily true for Float and Double, as NaN != NaN

@lrytz
Copy link
Member

lrytz commented Mar 7, 2018

I think you misunderstood what is meant, my comment was not very clear. there's no comparison involved. I updated my comment above.

@da-tubi
Copy link

da-tubi commented Jan 11, 2021 •
edited

See https://github.com/da-tubi/scala-optimizer/blob/master/ShortCircuitFold.scala

object ShortCircuitFold {
  def main(args: Array[String]): Unit = {
    val x = ((1 to 100).sum == 5050)
    val y = ((1 to 100).sum == 5051)
    val c1 = true || x
    val c2 = false && y 
    val c3 = true && x 
    val c4 = false || y
    val c5 = x && true
    val c6 = y || false 
    println(c1)
    println(c2)
    println(c3)
    println(c4)
    println(c5)
    println(c6)
  }
}

true || x ==> x

val c1 = true || x

// Default
      66: iconst_1
      67: ifne          74
      70: iload_2
      71: ifeq          78
      74: iconst_1
      75: goto          79
      78: iconst_0
      79: istore        4

// -opt:l:method
      66: iconst_1
      67: istore        4

// -opt:unreachable-code,simplify-jumps,compact-locals,copy-propagation
      66: iconst_1
      67: istore        4

// -opt:unreachable-code,simplify-jumps,compact-locals
      66: iconst_1
      67: pop
      68: iconst_1
      69: istore        4

// -opt:unreachable-code,simplify-jumps
      66: iconst_1
      67: pop
      68: iconst_1
      69: istore        4

// -opt:simplify-jumps
      66: iconst_1
      67: pop
      68: goto          75
      71: nop
      72: nop
      73: nop
      74: athrow
      75: iconst_1
      76: goto          80
      79: athrow
      80: istore        4

false && y ==> y

val c2 = false && y 

// Default
// -opt:l:method
      69: iconst_0
      70: istore        5

true && x ==> x

    val c3 = true && x 

      72: iload_2
      73: ifeq          80
      76: iconst_1
      77: goto          81
      80: iconst_0
      81: istore        6

@da-tubi
Copy link

da-tubi commented Jan 11, 2021

related: scala/scala-dev#29

@da-tubi
Copy link

da-tubi commented Jan 11, 2021

If x or y are constants, it will be folded during the typechecker phase, see scala/scala#9427

@SethTisue SethTisue added this to the Backlog milestone Sep 17, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement optimizer
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
5 participants
@lrytz @SethTisue @NthPortal @scabug @da-tubi