From 08ec6ba4e4aeb94f6505ecb462b94362ff0af096 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Tue, 29 Nov 2011 00:03:40 +0100 Subject: [vpm] optimized codegen avoids option-boxing introducing two mutable variables per pattern match: matchRes and keepGoing keepGoing denotes whether the result was Some or None, and matchRes holds the Some's contents or the right zero for the match's type Race(() => fastMatch(list), () => virtMatch_no_option(list))(100000).converge() is a virtual tie on my machine after this see https://gist.github.com/1400910 conveniently also works around SI-5245 don't assign to Unit-typed var's, in fact, make matchRes a val when its only prospect in life is to be unit-valued propagate eventual type for matchRes thru codegen so that we can have more robust checks for unit¬hing, when assignment makes no sense also, added a hack to caseResult to avoid boxed units in if(keepGoing) { matchRes = ... } else zero after erasure, we get if(keepGoing) { matchRes = ...; BoxedUNIT } else zero genicode broke because i was sharing trees: [scalacfork] error: java.lang.AssertionError: assertion failed: type error: can't convert from UNIT to REF(class Object) in unit ScalaSig.scala at source-/Users/adriaan/git/scala-dev/src/scalap/scala/tools/scalap/scalax/rules/scalasig/ScalaSig.scala,line-26,offset=868 fixed by duplicating -- so be it (for now -- make this more fine-grained, more efficient) dodging inliner issues with one/zero (it won't inline, so also directly inline those methods) --- src/compiler/scala/reflect/internal/TreeGen.scala | 29 +++- .../scala/tools/nsc/transform/UnCurry.scala | 39 +++--- .../tools/nsc/typechecker/PatMatVirtualiser.scala | 156 +++++++++++++++------ src/library/scala/MatchingStrategy.scala | 1 + 4 files changed, 160 insertions(+), 65 deletions(-) diff --git a/src/compiler/scala/reflect/internal/TreeGen.scala b/src/compiler/scala/reflect/internal/TreeGen.scala index 1c93a904c0..e537c6b83f 100644 --- a/src/compiler/scala/reflect/internal/TreeGen.scala +++ b/src/compiler/scala/reflect/internal/TreeGen.scala @@ -154,9 +154,13 @@ abstract class TreeGen { debuglog("casting " + tree + ":" + tree.tpe + " to " + pt + " at phase: " + phase) assert(!tree.tpe.isInstanceOf[MethodType], tree) assert(!pt.typeSymbol.isPackageClass && !pt.typeSymbol.isPackageObjectClass, pt) - // @MAT only called during erasure, which already takes care of that - // @PP: "only called during erasure" is not very true these days. - // In addition, at least, are: typer, uncurry, explicitouter, cleanup. + // called during (at least): typer, uncurry, explicitouter, cleanup. + // TODO: figure out the truth table for any/wrapInApply + // - the `any` flag seems to relate to erasure's adaptMember: "x.asInstanceOf[T] becomes x.$asInstanceOf[T]", + // where asInstanceOf is Any_asInstanceOf and $asInstanceOf is Object_asInstanceOf + // erasure will only unbox the value in a tree made by mkCast if `any && wrapInApply` + // - the `wrapInApply` flag need not be true if the tree will be adapted to have the empty argument list added before it gets to erasure + // in fact, I think it should be false for trees that will be type checked during typer assert(pt eq pt.normalize, tree +" : "+ debugString(pt) +" ~>"+ debugString(pt.normalize)) atPos(tree.pos)(mkAsInstanceOf(tree, pt, any = false, wrapInApply = true)) } @@ -262,6 +266,25 @@ abstract class TreeGen { tree setType tp } + def mkZeroContravariantAfterTyper(tp: Type): Tree = { + // contravariant -- for replacing an argument in a method call + // must use subtyping, as otherwise we miss types like `Any with Int` + val tree = + if (NullClass.tpe <:< tp) Literal(Constant(null)) + else if (UnitClass.tpe <:< tp) Literal(Constant()) + else if (BooleanClass.tpe <:< tp) Literal(Constant(false)) + else if (FloatClass.tpe <:< tp) Literal(Constant(0.0f)) + else if (DoubleClass.tpe <:< tp) Literal(Constant(0.0d)) + else if (ByteClass.tpe <:< tp) Literal(Constant(0.toByte)) + else if (ShortClass.tpe <:< tp) Literal(Constant(0.toShort)) + else if (IntClass.tpe <:< tp) Literal(Constant(0)) + else if (LongClass.tpe <:< tp) Literal(Constant(0L)) + else if (CharClass.tpe <:< tp) Literal(Constant(0.toChar)) + else mkCast(Literal(Constant(null)), tp) + + tree + } + /** Builds a tuple */ def mkTuple(elems: List[Tree]): Tree = if (elems.isEmpty) Literal(Constant()) diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index f319abd060..769ef79546 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -310,27 +310,34 @@ abstract class UnCurry extends InfoTransform case Apply(fun, List(a)) if fun.symbol == one => // blow one's argument away since all we want to know is whether the match succeeds or not // (the alternative, making `one` CBN, would entail moving away from Option) - val zero = // must use subtyping (no need for equality thanks to covariance), as otherwise we miss types like `Any with Int` - if (UnitClass.tpe <:< a.tpe) Literal(Constant()) - else if (BooleanClass.tpe <:< a.tpe) Literal(Constant(false)) - else if (FloatClass.tpe <:< a.tpe) Literal(Constant(0.0f)) - else if (DoubleClass.tpe <:< a.tpe) Literal(Constant(0.0d)) - else if (ByteClass.tpe <:< a.tpe) Literal(Constant(0.toByte)) - else if (ShortClass.tpe <:< a.tpe) Literal(Constant(0.toShort)) - else if (IntClass.tpe <:< a.tpe) Literal(Constant(0)) - else if (LongClass.tpe <:< a.tpe) Literal(Constant(0L)) - else if (CharClass.tpe <:< a.tpe) Literal(Constant(0.toChar)) - else { - val tpA = a.tpe.normalize - if (NullClass.tpe <:< tpA) NULL - else gen.mkCast(NULL, tpA) // must cast, at least when a.tpe <:< NothingClass.tpe - } - Apply(fun.duplicate, List(zero)) + Apply(fun.duplicate, List(gen.mkZeroContravariantAfterTyper(a.tpe))) case _ => super.transform(tree) } } substTree(Apply(Apply(TypeApply(Select(tgt.duplicate, tgt.tpe.member("isSuccess".toTermName)), targs map (_.duplicate)), args_scrut map (_.duplicate)), args_pm map (noOne.transform))) + // for no-option version of virtpatmat + case Block(List(zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats@_*), _) if opt.virtPatmat => import CODE._ + object dropMatchResAssign extends Transformer { + // override val treeCopy = newStrictTreeCopier // will duplicate below + override def transform(tree: Tree): Tree = tree match { + // don't compute the result of the match -- remove the caseResult block, except for the assignment to keepGoing + case Block(List(matchRes, ass@Assign(keepGoingLhs, falseLit)), zero) if keepGoingLhs.symbol eq keepGoing.symbol => + Block(List(ass), zero) + case _ => + super.transform(tree) + } + } + val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList + val idaBlock = Block( + zero :: + x :: + /* drop matchRes def */ + keepGoing :: + statsNoMatchRes, + NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` by `!keepGoing` + ) + substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed }) } diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala index c04e4796c4..05a85e97fe 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala @@ -88,9 +88,9 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => val scrutType = repeatedToSeq(elimAnonymousClass(scrut.tpe.widen)) val scrutSym = freshSym(scrut.pos, scrutType) - + val okPt = repeatedToSeq(pt) // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala with -Xexperimental - fixerUpper(context.owner, scrut.pos)(combineCases(scrut, scrutSym, cases map translateCase(scrutSym), repeatedToSeq(pt))) + fixerUpper(context.owner, scrut.pos)(combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt)) } @@ -122,8 +122,8 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => * a function that will take care of binding and substitution of the next ast (to the right). * */ - def translateCase(scrutSym: Symbol)(caseDef: CaseDef) = caseDef match { case CaseDef(pattern, guard, body) => - (translatePattern(scrutSym, pattern) ++ translateGuard(guard), translateBody(body)) + def translateCase(scrutSym: Symbol, pt: Type)(caseDef: CaseDef) = caseDef match { case CaseDef(pattern, guard, body) => + (translatePattern(scrutSym, pattern) ++ translateGuard(guard), translateBody(body, pt)) } def translatePattern(patBinder: Symbol, patTree: Tree): List[TreeMaker] = { @@ -245,7 +245,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // `one(x) : T` where x is the binder before this pattern, which will be replaced by the binder for the alternative by TreeMaker.singleBinder below // T is the widened type of the previous binder -- this ascription is necessary to infer a clean type for `or` -- the alternative combinator -- in the presence of existential types // see pos/virtpatmat_exist1.scala - combineExtractors(translatePattern(patBinder, alt), pmgen.one(CODE.REF(patBinder), patBinder.info.widen)) + combineExtractors(translatePattern(patBinder, alt), pmgen.one(CODE.REF(patBinder), patBinder.info.widen)) // only RHS of actual case should use caseResult, else the optimized codegen breaks } noFurtherSubPats(AlternativesTreeMaker(patBinder, altTrees : _*)) @@ -283,7 +283,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // so that we can return Option's from a match without ambiguity whether this indicates failure in the monad, or just some result in the monad // 2) body.tpe is the type of the body after applying the substitution that represents the solution of GADT type inference // need the explicit cast in case our substitutions in the body change the type to something that doesn't take GADT typing into account - def translateBody(body: Tree): Tree = atPos(body.pos)(pmgen.caseResult(body, body.tpe)) + def translateBody(body: Tree, matchPt: Type): Tree = atPos(body.pos)(pmgen.caseResult(body, body.tpe, matchPt)) /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// @@ -762,10 +762,15 @@ defined class Foo */ pmgen.or(wrapFunSubst(next), alts.toList) setPos alts.head.pos } - case class GuardTreeMaker(guardTree: Tree) extends SingleExtractorTreeMaker { + case class GuardTreeMaker(guardTree: Tree) extends /*SingleExtractor*/TreeMaker { val initialSubstitution: Substitution = EmptySubstitution - val nextBinder = freshSym(guardTree.pos, UnitClass.tpe) - val extractor = pmgen.guard(guardTree) + // val nextBinder = freshSym(guardTree.pos, UnitClass.tpe) + // val extractor = pmgen.guard(guardTree) + def chainBefore(next: Tree): Tree = { import CODE._ + IF (guardTree) THEN next ELSE pmgen.zero + } + + override def toString = "G("+ guardTree +")" } // combineExtractors changes the current substitution's of the tree makers in `treeMakers` @@ -901,7 +906,7 @@ defined class Foo */ } lazy val pmgen: CommonCodeGen with MatchingStrategyGen with MonadInstGen = - if (matchingMonadType.typeSymbol eq OptionClass) (new CommonCodeGen with MatchingStrategyGenOpt with MonadInstGenOpt {}) + if (matchingMonadType.typeSymbol eq OptionClass) (new CommonCodeGen with OptimizedCodeGen {}) else (new CommonCodeGen with MatchingStrategyGen with MonadInstGen {}) var ctr = 0 @@ -967,13 +972,13 @@ defined class Foo */ trait MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen => // methods in MatchingStrategy (the monad companion) -- used directly in translation def runOrElse(scrut: Tree, matcher: Tree, scrutTp: Type, resTp: Type): Tree = genTypeApply(matchingStrategy DOT vpmName.runOrElse, scrutTp, resTp) APPLY (scrut) APPLY (matcher) // matchingStrategy.runOrElse(scrut)(matcher) - def zero: Tree = matchingStrategy DOT vpmName.zero // matchingStrategy.zero - def one(res: Tree): Tree = one(res, NoType) + def zero: Tree = matchingStrategy DOT vpmName.zero // matchingStrategy.zero + def one(res: Tree): Tree = one(res, NoType) def one(res: Tree, tp: Type = NoType, oneName: Name = vpmName.one): Tree = genTypeApply(matchingStrategy DOT oneName, tp) APPLY (res) // matchingStrategy.one(res) - def or(f: Tree, as: List[Tree]): Tree = (matchingStrategy DOT vpmName.or)((f :: as): _*) // matchingStrategy.or(f, as) - def guard(c: Tree): Tree = (matchingStrategy DOT vpmName.guard)(c, UNIT) // matchingStrategy.guard(c, then) -- a user-defined guard + def or(f: Tree, as: List[Tree]): Tree = (matchingStrategy DOT vpmName.or)((f :: as): _*) // matchingStrategy.or(f, as) + def guard(c: Tree): Tree = (matchingStrategy DOT vpmName.guard)(c, UNIT) // matchingStrategy.guard(c, then) -- a user-defined guard // TODO: get rid of the cast when it's unnecessary, but this requires type checking `body` -- maybe this should be one of the optimisations we perform after generating the tree - def caseResult(res: Tree, tp: Type): Tree = (matchingStrategy DOT vpmName.caseResult) (_asInstanceOf(res, tp, force = true)) // matchingStrategy.caseResult(res), like one, but blow this one away for isDefinedAt (since it's the RHS of a case) + def caseResult(res: Tree, bodyPt: Type, matchPt: Type): Tree = (matchingStrategy DOT vpmName.caseResult) (_asInstanceOf(res, bodyPt, force = true)) // matchingStrategy.caseResult(res), like one, but blow this one away for isDefinedAt (since it's the RHS of a case) // an internal guard TODO: use different method call so exhaustiveness can distinguish it from user-defined guards def cond(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = genTypeApply((matchingStrategy DOT vpmName.guard), repackExistential(tp)) APPLY (c, then) // matchingStrategy.guard(c, then) @@ -991,30 +996,98 @@ defined class Foo */ // `o.flatMap(f)` becomes `if(o == None) None else f(o.get)`, similarly for orElse and guard // this is a special instance of the advanced inlining optimization that takes a method call on // an object of a type that only has two concrete subclasses, and inlines both bodies, guarded by an if to distinguish the two cases - trait MatchingStrategyGenOpt extends MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen => + trait OptimizedCodeGen extends CommonCodeGen with MatchingStrategyGen with MonadInstGen { override def guard(c: Tree): Tree = condOptimized(c, one(UNIT)) override def cond(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = condOptimized(c, one(then, repackExistential(tp))) - // override def runOrElse(scrut: Tree, matcher: Tree): Tree = matcher match { - // case Function(List(x: ValDef), body) => - // val tp = x.symbol.tpe - // val restp = appliedType(matchingMonadType, List(pt)) // don't always know pt.... - // val isEmpty = restp member vpmName.isEmpty - // val get = restp member vpmName.get - // - // val vs = freshSym(scrut.pos, tp, "s") - // val vres = freshSym(scrut.pos, restp, "res") - // val s = VAL(vs) === scrut - // val res = VAL(vres) === typedSubst(body, List(x.symbol), List(REF(vs))) - // - // BLOCK( - // s, - // res, - // IF (res DOT isEmpty) THEN ELSE (res DOT get) - // ) - // } - } - trait MonadInstGenOpt extends MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen => + lazy val zeroSym = freshSym(NoPosition, optionType(NothingClass.tpe), "zero") + override def zero: Tree = REF(zeroSym) + override def one(res: Tree, tp: Type = NoType, oneName: Name = vpmName.one): Tree = Apply(genTypeApply(REF(SomeModule), tp), List(res)) + + // duplicated out of frustration with cast generation + private def mkZero(tp: Type): Tree = { + tp.typeSymbol match { + case UnitClass => Literal(Constant()) + case BooleanClass => Literal(Constant(false)) + case FloatClass => Literal(Constant(0.0f)) + case DoubleClass => Literal(Constant(0.0d)) + case ByteClass => Literal(Constant(0.toByte)) + case ShortClass => Literal(Constant(0.toShort)) + case IntClass => Literal(Constant(0)) + case LongClass => Literal(Constant(0L)) + case CharClass => Literal(Constant(0.toChar)) + case _ => gen.mkAsInstanceOf(Literal(Constant(null)), tp, any = true, wrapInApply = false) // the magic incantation is true/false here + } + } + + + /** Inline runOrElse and get rid of Option allocations + * + * runOrElse(scrut: scrutTp)(matcher): resTp = matcher(scrut) getOrElse (throw new MatchError(x)) + * the matcher's optional result is encoded as a flag, keepGoing, where keepGoing == true encodes result.isEmpty, + * if keepGoing is false, the result Some(x) of the naive translation is encoded as matchRes == x + */ + @inline private def dontStore(tp: Type) = (tp.typeSymbol eq UnitClass) || (tp.typeSymbol eq NothingClass) + lazy val keepGoing = freshSym(NoPosition, BooleanClass.tpe, "keepGoing") setFlag MUTABLE + lazy val matchRes = freshSym(NoPosition, AnyClass.tpe, "matchRes") setFlag MUTABLE + override def runOrElse(scrut: Tree, matcher: Tree, scrutTp: Type, resTp: Type) = matcher match { + case Function(List(x: ValDef), body) => + matchRes.info = if (resTp ne NoType) resTp.widen else AnyClass.tpe // we don't always know resTp, and it might be AnyVal, in which case we can't assign NULL + if (dontStore(resTp)) matchRes resetFlag MUTABLE // don't assign to Unit-typed var's, in fact, make it a val -- conveniently also works around SI-5245 + BLOCK( + VAL(zeroSym) === REF(NoneModule), // TODO: can we just get rid of explicitly emitted zero? don't know how to do that as a local rewrite... + VAL(x.symbol) === scrut, // reuse the symbol of the function's argument to avoid creating a fresh one and substituting it for x.symbol in body -- the owner structure is repaired by fixerUpper + VAL(matchRes) === mkZero(matchRes.info), // must cast to deal with GADT typing, hence the private mkZero above + VAL(keepGoing) === TRUE, + body, + IF (REF(keepGoing)) THEN MATCHERROR(REF(x.symbol)) ELSE REF(matchRes) + ) + } + + override def caseResult(res: Tree, bodyPt: Type, matchPt: Type): Tree = { + BLOCK( + if (dontStore(matchPt)) res // runOrElse hasn't been called yet, so matchRes.isMutable is irrelevant, also, tp may be a subtype of resTp used in runOrElse... + else (REF(matchRes) === res), // _asInstanceOf(res, tp.widen, force = true) + REF(keepGoing) === FALSE, + zero // to have a nice lub for lubs -- otherwise we'll get a boxed unit here -- TODO: get rid of all those dangling else zero's + ) + } + + override def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = { + BLOCK( + thisCase, + IF (REF(keepGoing)) THEN elseCase ELSE zero // leave trailing zero for now, otherwise typer adds () anyway + ) + } + + /* TODO: make more efficient -- + val i = 0 + while(keepGoing && i < alts.length) { + val altOpt = @switch i match { case 0 => alt_0 .... case alts.length-1 => alt_N-1 } + if (altOpt ne zero) { + val alt = altOpt.get + nextBody + } + i += 1 + } + */ + override def or(next: Tree, alts: List[Tree]): Tree = { + val Function(List(nextVD: ValDef), nextBody) = next + val thunks = (REF(ListModule) DOT List_apply) APPLY (alts map (Function(Nil, _))) + val alt = nextVD.symbol + val altTp = alt.info + val altThunk = freshSym(alts.head.pos, functionType(List(), optionType(altTp)), "altThunk") + val altOpt = freshSym(alts.head.pos, optionType(altTp), "altOpt") + val altGet = optionType(altTp) member vpmName.get + + (thunks DOT "dropWhile".toTermName) APPLY (Function(List(ValDef(altThunk)), + BLOCK( + VAL(altOpt) === (REF(altThunk) APPLY ()), + IF (REF(altOpt) OBJ_NE zero) THEN BLOCK(VAL(alt) === (REF(altOpt) DOT altGet), nextBody) ENDIF, + REF(keepGoing) + ))) + } + override def flatMap(opt: Tree, fun: Tree): Tree = fun match { case Function(List(x: ValDef), body) => val tp = appliedType(matchingMonadType, List(x.symbol.tpe)) @@ -1025,20 +1098,11 @@ defined class Foo */ BLOCK( v, - IF (vs DOT isEmpty) THEN zero ELSE typedSubst(body, List(x.symbol), List(vs DOT get)) + IF (vs DOT isEmpty) THEN zero ELSE typedSubst(body, List(x.symbol), List(vs DOT get)) // must be isEmpty and get as we don't control the target of the call (could be the result of a user-defined extractor) ) case _ => println("huh?") (opt DOT vpmName.flatMap)(fun) } - override def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = { - val vs = freshSym(thisCase.pos, pt, "o") - val isEmpty = pt member vpmName.isEmpty - val v = VAL(vs) === thisCase // genTyped(, pt) - BLOCK( - v, - IF (vs DOT isEmpty) THEN elseCase /*genTyped(, pt)*/ ELSE REF(vs) - ) - } } def genTypeApply(tfun: Tree, args: Type*): Tree = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree) diff --git a/src/library/scala/MatchingStrategy.scala b/src/library/scala/MatchingStrategy.scala index 4eaf7852b8..2c713e4850 100644 --- a/src/library/scala/MatchingStrategy.scala +++ b/src/library/scala/MatchingStrategy.scala @@ -10,6 +10,7 @@ abstract class MatchingStrategy[M[+x]] { // find the first alternative to successfully flatMap f // to avoid code explosion due to alternatives + // TODO: should be alts: => M[T]* def or[T, U](f: T => M[U], alts: M[T]*) = (alts foldLeft (zero: M[U]))(altFlatMap(f)) def caseResult[T](x: T): M[T] = one(x) // used as a marker to distinguish the RHS of a case (case pat => RHS) and intermediate successes -- cgit v1.2.3