| Commit message (Collapse) | Author | Age | Files | Lines |
| |
|
|\
| |
| | |
Closure elimination for new backend
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
ASM has a built-in `SourceValue` analysis which computes for each
value a set of instructions that may possibly have constructed it.
The ProdConsAnalyzer class provides additional queries over the
result of the SourceValue analysis:
- consumers of values
- tracking producers / consumers through copying operations (load,
store, etc)
A fix to (and therefore a new version of) ASM was required. See here:
https://github.com/scala/scala-asm/commit/94106a5472
|
|/ |
|
|\
| |
| | |
Fix illegal inlining of instructions accessing protected members
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
There were two issues in the new inliner that would cause a
VerifyError and an IllegalAccessError.
First, an access to a public member of package protected class C can
only be inlined if the destination class can access C. This is tested
by t7582b.
Second, an access to a protected member requires the receiver object
to be a subtype of the class where the instruction is located. So
when inlining such an access, we need to know the type of the receiver
object - which we don't have. Therefore we don't inline in this case
for now. This can be fixed once we have a type propagation analyis.
https://github.com/scala-opt/scala/issues/13.
This case is tested by t2106.
Force kmpSliceSearch test to delambdafy:inline
See discussion on https://github.com/scala/scala/pull/4505. The issue
will go away when moving to indy-lambda.
|
|\ \
| | |
| | | |
fix BigDecimal losing MathContext
|
| | | |
|
| | | |
|
| |/ |
|
| |
| |
| |
| |
| | |
Fix exclusive floating point ranges to contain also the last element
when the end-start difference is not an integer multiple of step.
|
|\ \
| | |
| | | |
Clean implementation of sorts for scala.util.Sorting.
|
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Removed code based on Sun JDK sorts and implemented new (basic) sorts from
scratch. Deferred to Java Arrays.sort whenever practical. Behavior of
`scala.util.Sorting` should be unchanged, but changed documentation to
specify when the Java methods are being used (as they're typically very fast).
A JUnit test is provided.
Performance is important for sorts. Everything is better with this patch,
though it could be better yet, as described below.
Below are sort times (in microseconds, SEM < 5%) for various 1024-element
arrays of small case classes that compare on an int field (quickSort), or
int arrays that use custom ordering (stableSort). Note: "degenerate"
means there are only 16 values possible, so there are lots of ties.
Times are all with fresh data (no re-using cache from run to run).
Results:
```
random sorted reverse degenerate big:64k tiny:16
Old Sorting.quickSort 234 181 178 103 25,700 1.4
New Sorting.quickSort 170 27 115 74 18,600 0.8
Old Sorting.stableSort 321 234 236 282 32,600 2.1
New Sorting.stableSort 239 16 194 194 25,100 1.2
java.util.Arrays.sort 124 4 8 105 13,500 0.8
java.util.Arrays.sort|Box 126 15 13 112 13,200 0.9
```
The new versions are uniformly faster, but uniformly slower than Java sorting. scala.util.Sorting has use cases that don't map easily in to Java unless everything is pre-boxed, but the overhead of pre-boxing is minimal compared to the sort.
A snapshot of some of my benchmarking code is below.
(Yes, lots of repeating myself--it's dangerous not to when trying to get
somewhat accurate benchmarks.)
```
import java.util.Arrays
import java.util.Comparator
import math.Ordering
import util.Sorting
import reflect.ClassTag
val th = ichi.bench.Thyme.warmed()
case class N(i: Int, j: Int) {}
val a = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt, i)) )
var ai = 0
val b = Array.fill(1024)( Array.tabulate(1024)(i => N(i, i)) )
var bi = 0
val c = Array.fill(1024)( Array.tabulate(1024)(i => N(1024-i, i)) )
var ci = 0
val d = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt(16), i)) )
var di = 0
val e = Array.fill(16)( Array.tabulate(65536)(i => N(util.Random.nextInt, i)) )
var ei = 0
val f = Array.fill(65535)( Array.tabulate(16)(i => N(util.Random.nextInt, i)) )
var fi = 0
val o = new Ordering[N]{ def compare(a: N, b: N) = if (a.i < b.i) -1 else if (a.i > b.i) 1 else 0 }
for (s <- Seq("one", "two", "three")) {
println(s)
th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Sorting.quickSort(x)(o); x(x.length/3) }
}
def ix(ns: Array[N]) = {
val is = new Array[Int](ns.length)
var i = 0
while (i < ns.length) {
is(i) = ns(i).i
i += 1
}
is
}
val p = new Ordering[Int]{ def compare(a: Int, b: Int) = if (a > b) 1 else if (a < b) -1 else 0 }
for (s <- Seq("one", "two", "three")) {
println(s)
val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
th.pbench{ val x = ix(a(ai)); ai = (ai+1)%a.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(b(bi)); bi = (bi+1)%b.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(c(ci)); ci = (ci+1)%c.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(d(di)); di = (di+1)%d.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(e(ei)); ei = (ei+1)%e.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(f(fi)); fi = (fi+1)%f.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
}
for (s <- Seq("one", "two", "three")) {
println(s)
th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Arrays.sort(x, o); x(x.length/3) }
}
def bx(is: Array[Int]): Array[java.lang.Integer] = {
val Is = new Array[java.lang.Integer](is.length)
var i = 0
while (i < is.length) {
Is(i) = java.lang.Integer.valueOf(is(i))
i += 1
}
Is
}
def xb(Is: Array[java.lang.Integer]): Array[Int] = {
val is = new Array[Int](Is.length)
var i = 0
while (i < is.length) {
is(i) = Is(i).intValue
i += 1
}
is
}
val q = new Comparator[java.lang.Integer]{
def compare(a: java.lang.Integer, b: java.lang.Integer) = o.compare(a.intValue, b.intValue)
}
for (s <- Seq("one", "two", "three")) {
println(s)
val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
th.pbench{ val x = bx(ix(a(ai))); ai = (ai+1)%a.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(b(bi))); bi = (bi+1)%b.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(c(ci))); ci = (ci+1)%c.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(d(di))); di = (di+1)%d.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(e(ei))); ei = (ei+1)%e.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(f(fi))); fi = (fi+1)%f.length; Arrays.sort(x, q); xb(x)(x.length/3) }
}
```
|
|\ \ \
| |/ /
|/| | |
Nullness Analysis for GenBCode
|
| | | |
|
| | |
| | |
| | |
| | |
| | |
| | | |
Address feedback in #4516 / 57b8da4cd8. Save allocations of
NullnessValue - there's only 4 possible instances. Also save tuple
allocations in InstructionStackEffect.
|
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
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.
|
| |/
| |
| |
| |
| |
| |
| |
| | |
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.
|
|/
|
|
|
|
|
|
|
|
|
|
|
| |
Since the leading and trailing iterators returned by span
share the underlying iterator, the leading iterator must
flag when it is exhausted (when the span predicate fails)
since the trailing iterator will advance the underlying
iterator.
It would also be possible to leave the failing element in
the leading lookahead buffer, where it would forever fail
the predicate, but that entails evaluating the predicate
twice, on both enqueue and dequeue.
|
|\
| |
| | |
SI-9254 UnrolledBuffer appends in wrong position
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Fixed two bugs in insertion (insertAll of Unrolled):
1. Incorrect recursion leading to an inability to insert past the first chunk
2. Incorect repositioning of `lastptr` leading to strange `append` behavior after early insertion
Added tests checking that both of these things now work.
Also added a comment that "waterlineDelim" is misnamed. But we can't fix it now--it's part of the public API. (Shouldn't be, but it is.)
|
|\ \
| | |
| | | |
SI-9197 Duration.Inf not a singleton when deserialized
|
| |/
| |
| |
| |
| |
| |
| |
| | |
Made `Duration.Undefined`, `.Inf`, and `.MinusInf` all give back the singleton instance instead of creating a new copy by overriding readResolve.
This override can be (and is) private, which at least on Sun's JDK8 doesn't mess with the auto-generated SerialVersionUIDs.
Thus, the patch should make things strictly better: if you're on 2.11.7+ on JVMs which pick the same SerialVersionUIDs, you can recover singletons. Everywhere else you were already in trouble anyway.
|
|\ \
| | |
| | | |
SI-9275 Fix row-first display in REPL
|
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
A missing range check in case anyone ever wants to use
```
-Dscala.repl.format=across
```
which was observed only because of competition from Ammonite.
|
|\ \ \
| | | |
| | | | |
Fix many typos
|
| |/ /
| | |
| | |
| | |
| | | |
This commit corrects many typos found in scaladocs and comments.
There's also fixed the name of a private method in ICodeCheckers.
|
|/ / |
|
|\ \
| | |
| | | |
Patmat: efficient reasoning about mutual exclusion
|
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Faster analysis of wide (but relatively flat) class hierarchies
by using a more efficient encoding of mutual exclusion.
The old CNF encoding for mutually exclusive symbols of a domain
added a quadratic number of clauses to the formula to satisfy.
E.g. if a domain has the symbols `a`, `b` and `c` then
the clauses
```
!a \/ !b /\
!a \/ !c /\
!b \/ !c
```
were added.
The first line prevents that `a` and `b` are both true at the same time, etc.
There's a simple, more efficient encoding that can be used instead: consider a
comparator circuit in hardware, that checks that out of `n` signals, at most 1
is true. Such a circuit can be built in the form of a sequential counter and
thus requires only 3n-4 additional clauses [1]. A comprehensible comparison of
different encodings can be found in [2].
[1]: http://www.carstensinz.de/papers/CP-2005.pdf
[2]: http://www.wv.inf.tu-dresden.de/Publications/2013/report-13-04.pdf
|
|\ \ \
| |/ /
|/| | |
Fixes and Improvements for the new inliner
|
| | |
| | |
| | |
| | | |
Cannot inline if one of the methods is @strictfp, but not the other.
|
| | |
| | |
| | |
| | |
| | | |
Invocations of private methods cannot be inlined into a different
class, this would cause an IllegalAccessError.
|
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Many backend components don't have access to the compiler instance
holding the settings.
Before this change, individual settings required in these parts of the
backend were made available as members of trait BTypes, implemented
in the subclass BTypesFromSymbols (which has access to global).
This change exposes a single value of type ScalaSettings in the super
trait BTypes, which gives access to all compiler settings.
|
| | |
| | |
| | |
| | | |
Because you can't, really.
|
| |/
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Running an ASM analyzer returns null frames for unreachable
instructions in the analyzed method. The inliner (and other components
of the optimizer) require unreachable code to be eliminated to avoid
null frames.
Before this change, unreachable code was eliminated before building
the call graph, but not again before inlining: the inliner assumed
that methods in the call graph have no unreachable code.
This invariant can break when inlining a method. Example:
def f = throw e
def g = f; println()
When building the call graph, both f and g contain no unreachable
code. After inlining f, the println() call becomes unreachable. This
breaks the inliner's assumption if it tries to inline a call to g.
This change intruduces a cache to remember methods that have no
unreachable code. This allows invoking DCE every time no dead code is
required, and bail out fast. This also simplifies following the
control flow in the optimizer (call DCE whenever no dead code is
required).
|
|\ \
| |/
|/| |
SI-9181 Exhaustivity checking does not scale (regression)
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
reachability analysis are too big to be solved in reasonable time, then we skip
the analysis. I also cleaned up warnings.
Why did `t9181.scala` work fine with 2.11.4, but is now running out of memory?
In order to ensure that the scrutinee is associated only with one of the 400
derived classes we add 400*400 / 2 ~ 80k clauses to ensure mutual exclusivity.
In 2.11.4 the translation into CNF used to fail, since it would blow up already
at this point in memory. This has been fixed in 2.11.5, but now the DPLL solver
is the bottleneck.
There's a check in the search for all models (exhaustivity) that it would avoid
a blow up, but in the search for a model (reachability), such a check is
missing.
|
|\ \
| | |
| | | |
Remove deprecation warnings
|
| | | |
|
|/ /
| |
| |
| |
| |
| |
| |
| | |
Syntax highlightning in code blocks used to manipulate the raw bytes of
a String, converting them to chars when needed, which breaks Unicode
surrogate pairs.
Using a char array instead of a byte array will leave them alone.
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Method bodies that contain a super call cannot be inlined into other
classes. The same goes for methods containing calls to private
methods, but that was already ensured before by accessibility checks.
The last case of `invokespecial` instructions is constructor calls.
Those can be safely moved into different classes (as long as the
constructor is accessible at the new location).
Note that scalac never emits methods / constructors as private in
bytecode.
|
| | |
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
The inliner would incorrectly treat trait field accessors like
ordinary trait member methods and try to re-write invocations to the
corresponding static method in the implementation class. This rewrite
usually failed because no method was found in the impl class.
However, for lazy val fields, there exists a member in the impl class
with the same name, and the rewrite was performed. The result was that
every field access would execute the lazy initializer instead of
reading the field.
This commit checks the traitMethodWithStaticImplementation field of
the ScalaInlineInfo classfile attribute and puts an explicit
`safeToRewrite` flag to each call site in the call graph. This cleans
up the code in the inliner that deals with rewriting trait callsites.
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Issue precise warnings when the inliner fails to inline or analyze a
callsite. Inline failures may have various causes, for example because
some class cannot be found on the classpath when building the call
graph. So we need to store problems that happen early in the optimizer
(when building the necessary data structures, call graph, ClassBTypes)
to be able to report them later in case the inliner accesses the
related data.
We use Either to store these warning messages. The commit introduces
an implicit class `RightBiasedEither` to make Either easier to use for
error propagation. This would be subsumed by a biased either in the
standard library (or could use a Validation).
The `info` of each ClassBType is now an Either. There are two cases
where the info is not available:
- The type info should be parsed from a classfile, but the class
cannot be found on the classpath
- SI-9111, the type of a Java source originating class symbol cannot
be completed
This means that the operations on ClassBType that query the info now
return an Either, too.
Each Callsite in the call graph now stores the source position of the
call instruction. Since the call graph is built after code generation,
we build a map from invocation nodes to positions during code gen and
query it when building the call graph.
The new inliner can report a large number of precise warnings when a
callsite cannot be inlined, or if the inlining metadata cannot be
computed precisely, for example due to a missing classfile.
The new -Yopt-warnings multi-choice option allows configuring inliner
warnings.
By default (no option provided), a one-line summary is issued in case
there were callsites annotated @inline that could not be inlined.
|
| |
| |
| |
| |
| | |
I observed cases (eg Scaladoc tests) where we end up with 17k+
ClassNodes, which makes 500 MB.
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
The self parameter type may be incompatible with the trait type.
trait T { self: S => def foo = 1 }
The $self parameter type of T$class.foo is S, which may be unrelated
to T. If we re-write a call to T.foo to T$class.foo, we need to cast
the receiver to S, otherwise we get a VerifyError.
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
In order to inline a final trait method, callsites of such methods are
first re-written from interface calls to static calls of the trait's
implementation class. Then inlining proceeds as ususal.
One problem that came up during development was that mixin methods are
added to class symbols only for classes being compiled, but not for
others. In order to inline a mixin method, we need the InlineInfo,
which so far was built using the class (and method) symbols. So we had
a problem with separate compilation.
Looking up the symbol from a given classfile name was already known to
be brittle (it's also one of the weak points of the current inliner),
so we changed the strategy. Now the InlineInfo for every class is
encoded in a new classfile attribute.
This classfile attribute is relatively small, because all strings it
references (class internal names, method names, method descriptors)
would exist anyway in the constant pool, so it just adds a few
references.
When building the InlineInfo for a class symbol, we only look at the
symbol properties for symbols being compiled in the current run. For
unpickled symbols, we build the InlineInfo by reading the classfile
attribute.
This change also adds delambdafy:method classes to currentRun.symSource.
Otherwise, currentRun.compiles(lambdaClass) is false.
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
In mixed compilation, the bytecode of Java classes is not availalbe:
the Scala compiler does not produce any, and there are no classfiles
yet.
When inlining a (Scala defined) method that contains an invocation to
a Java method, we need the Java method's bytecode in order to check
whether that invocation can be transplanted to the new location
without causing an IllegalAccessError. If the bytecode cannot be
found, inlining won't be allowed.
|
| |
| |
| |
| |
| |
| |
| | |
The `ByteCodeRepository.classNode(InternalName)` method now returns an
option. Concretely, in mixed compilation, the compiler does not create
a ClassNode for Java classes, and they may not exist on the classpath
either.
|