diff options
author | Paul Phillips <paulp@improving.org> | 2012-02-17 11:13:26 -0800 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2012-02-17 11:13:26 -0800 |
commit | 35b81d14778d2c6e8392ae51c53652f48b52b488 (patch) | |
tree | 7a51b75ac05953b73f652257871613254ee18a5f | |
parent | 1e648c386216d4c60121321a7ec40e2536bada9c (diff) | |
parent | 7de7f13d9d60a0cfc67f63a5fa9d6f79b6a9a392 (diff) | |
download | scala-35b81d14778d2c6e8392ae51c53652f48b52b488.tar.gz scala-35b81d14778d2c6e8392ae51c53652f48b52b488.tar.bz2 scala-35b81d14778d2c6e8392ae51c53652f48b52b488.zip |
Merge branch 'develop'
19 files changed, 1083 insertions, 548 deletions
diff --git a/src/compiler/scala/reflect/internal/StdNames.scala b/src/compiler/scala/reflect/internal/StdNames.scala index 1f67bbc0ac..b4c404a80c 100644 --- a/src/compiler/scala/reflect/internal/StdNames.scala +++ b/src/compiler/scala/reflect/internal/StdNames.scala @@ -330,6 +330,7 @@ trait StdNames extends NameManglers { self: SymbolTable => val freeValue : NameType = "freeValue" val genericArrayOps: NameType = "genericArrayOps" val get: NameType = "get" + val getOrElse: NameType = "getOrElse" val hasNext: NameType = "hasNext" val hashCode_ : NameType = if (forMSIL) "GetHashCode" else "hashCode" val hash_ : NameType = "hash" diff --git a/src/compiler/scala/tools/nsc/ast/TreeGen.scala b/src/compiler/scala/tools/nsc/ast/TreeGen.scala index 265d017653..3467292f28 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeGen.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeGen.scala @@ -13,7 +13,7 @@ import symtab.SymbolTable /** XXX to resolve: TreeGen only assumes global is a SymbolTable, but * TreeDSL at the moment expects a Global. Can we get by with SymbolTable? */ -abstract class TreeGen extends reflect.internal.TreeGen { +abstract class TreeGen extends reflect.internal.TreeGen with TreeDSL { val global: Global import global._ @@ -66,18 +66,81 @@ abstract class TreeGen extends reflect.internal.TreeGen { case _ => tree } - def withDefaultCase(matchExpr: Tree, defaultAction: Tree/*scrutinee*/ => Tree): Tree = matchExpr match { - case Match(scrutinee, cases) => - if (cases exists treeInfo.isDefaultCase) matchExpr - else { - val defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, defaultAction(scrutinee)) - Match(scrutinee, cases :+ defaultCase) + // must be kept in synch with the codegen in PatMatVirtualiser + object VirtualCaseDef { + def unapply(b: Block): Option[(Assign, Tree, Tree)] = b match { + case Block(List(assign@Assign(keepGoingLhs, falseLit), matchRes), zero) => Some((assign, matchRes, zero)) // TODO: check tree annotation + case _ => None + } + } + + // TODO: would be so much nicer if we would know during match-translation (i.e., type checking) + // whether we should emit missingCase-style apply (and isDefinedAt), instead of transforming trees post-factum + class MatchMatcher { + def caseMatch(orig: Tree, selector: Tree, cases: List[CaseDef], wrap: Tree => Tree): Tree = unknownTree(orig) + def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = unknownTree(orig) + def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree): Tree = unknownTree(orig) + + def apply(matchExpr: Tree): Tree = (matchExpr: @unchecked) match { + // old-style match or virtpatmat switch + case Match(selector, cases) => // println("simple match: "+ (selector, cases) + "for:\n"+ matchExpr ) + caseMatch(matchExpr, selector, cases, identity) + // old-style match or virtpatmat switch + case Block((vd: ValDef) :: Nil, orig@Match(selector, cases)) => // println("block match: "+ (selector, cases, vd) + "for:\n"+ matchExpr ) + caseMatch(matchExpr, selector, cases, m => copyBlock(matchExpr, List(vd), m)) + // virtpatmat + case Apply(Apply(TypeApply(Select(tgt, nme.runOrElse), targs), List(scrut)), List(matcher)) if opt.virtPatmat => // println("virt match: "+ (tgt, targs, scrut, matcher) + "for:\n"+ matchExpr ) + caseVirtualizedMatch(matchExpr, tgt, targs, scrut, matcher) + // optimized version of virtpatmat + case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, epilogue) if opt.virtPatmat => // TODO: check tree annotation // println("virtopt match: "+ (zero, x, matchRes, keepGoing, stats) + "for:\n"+ matchExpr ) + caseVirtualizedMatchOpt(matchExpr, zero, x, matchRes, keepGoing, stats, epilogue, identity) + // optimized version of virtpatmat + case Block(outerStats, orig@Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, epilogue)) if opt.virtPatmat => // TODO: check tree annotation // println("virt opt block match: "+ (zero, x, matchRes, keepGoing, stats, outerStats) + "for:\n"+ matchExpr ) + caseVirtualizedMatchOpt(matchExpr, zero, x, matchRes, keepGoing, stats, epilogue, m => copyBlock(matchExpr, outerStats, m)) + case other => + unknownTree(other) + } + + def unknownTree(t: Tree): Tree = throw new MatchError(t) + def copyBlock(orig: Tree, stats: List[Tree], expr: Tree): Block = Block(stats, expr) + + def dropSyntheticCatchAll(cases: List[CaseDef]): List[CaseDef] = + if (!opt.virtPatmat) cases + else cases filter { + case CaseDef(pat, EmptyTree, Throw(Apply(Select(New(exTpt), nme.CONSTRUCTOR), _))) if (treeInfo.isWildcardArg(pat) && (exTpt.tpe.typeSymbol eq MatchErrorClass)) => false + case CaseDef(pat, guard, body) => true + } + } + + def withDefaultCase(matchExpr: Tree, defaultAction: Tree/*scrutinee*/ => Tree): Tree = { + object withDefaultTransformer extends MatchMatcher { + override def caseMatch(orig: Tree, selector: Tree, cases: List[CaseDef], wrap: Tree => Tree): Tree = { + val casesNoSynthCatchAll = dropSyntheticCatchAll(cases) + if (casesNoSynthCatchAll exists treeInfo.isDefaultCase) orig + else { + val defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, defaultAction(selector.duplicate)) + wrap(Match(selector, casesNoSynthCatchAll :+ defaultCase)) + } + } + override def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = { import CODE._ + ((matcher APPLY (scrut)) DOT nme.getOrElse) APPLY (defaultAction(scrut.duplicate)) // TODO: pass targs } - case _ => - matchExpr - // [Martin] Adriaan: please fill in virtpatmat transformation here + override def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree): Tree = { import CODE._ + wrap(Block( + zero :: + x :: + matchRes :: + keepGoing :: + stats, + // replace `if (keepGoing) throw new MatchError(...) else matchRes` by `if (keepGoing) ${defaultAction(`x`)} else matchRes` + (IF (REF(keepGoing.symbol)) THEN defaultAction(x.rhs.duplicate) ELSE REF(matchRes.symbol)) + )) + } + } + withDefaultTransformer(matchExpr) } + def mkCached(cvar: Symbol, expr: Tree): Tree = { val cvarRef = mkUnattributedRef(cvar) Block( diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala index 6aee52a354..f2c725a5c2 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala @@ -393,15 +393,15 @@ abstract class GenICode extends SubComponent { for (CaseDef(pat, _, body) <- catches.reverse) yield { def genWildcardHandler(sym: Symbol): (Symbol, TypeKind, Context => Context) = (sym, kind, ctx => { - ctx.bb.emit(DROP(REFERENCE(sym))) + ctx.bb.emit(DROP(REFERENCE(sym))) // drop the loaded exception genLoad(body, ctx, kind) }) pat match { case Typed(Ident(nme.WILDCARD), tpt) => genWildcardHandler(tpt.tpe.typeSymbol) case Ident(nme.WILDCARD) => genWildcardHandler(ThrowableClass) - case Bind(name, _) => - val exception = ctx.method addLocal new Local(pat.symbol, toTypeKind(pat.symbol.tpe), false) + case Bind(_, _) => + val exception = ctx.method addLocal new Local(pat.symbol, toTypeKind(pat.symbol.tpe), false) // the exception will be loaded and stored into this local (pat.symbol.tpe.typeSymbol, kind, { ctx: Context => @@ -1054,7 +1054,7 @@ abstract class GenICode extends SubComponent { case Match(selector, cases) => debuglog("Generating SWITCH statement."); - var ctx1 = genLoad(selector, ctx, INT) + var ctx1 = genLoad(selector, ctx, INT) // TODO: Java 7 allows strings in switches (so, don't assume INT and don't convert the literals using intValue) val afterCtx = ctx1.newBlock var caseCtx: Context = null generatedType = toTypeKind(tree.tpe) @@ -2086,12 +2086,12 @@ abstract class GenICode extends SubComponent { exh }) else None - val exhs = handlers.map { handler => - val exh = this.newExceptionHandler(handler._1, handler._2, tree.pos) + val exhs = handlers.map { case (sym, kind, handler) => // def genWildcardHandler(sym: Symbol): (Symbol, TypeKind, Context => Context) = + val exh = this.newExceptionHandler(sym, kind, tree.pos) var ctx1 = outerCtx.enterExceptionHandler(exh) ctx1.addFinalizer(finalizer, finalizerCtx) loadException(ctx1, exh, tree.pos) - ctx1 = handler._3(ctx1) + ctx1 = handler(ctx1) // emit finalizer val ctx2 = emitFinalizer(ctx1) ctx2.bb.closeWith(JUMP(afterCtx.bb)) diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala index 60cb679782..9f43e1b84c 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -60,20 +60,17 @@ trait DataFlowAnalysis[L <: SemiLattice] { val output = f(point, in(point)) if ((lattice.bottom == out(point)) || output != out(point)) { -// Console.println("Output changed at " + point -// + " from: " + out(point) + " to: " + output -// + " for input: " + in(point) + " and they are different: " + (output != out(point))) + // Console.println("Output changed at " + point + // + " from: " + out(point) + " to: " + output + // + " for input: " + in(point) + " and they are different: " + (output != out(point))) out(point) = output val succs = point.successors succs foreach { p => - if (!worklist(p)) - worklist += p; - if (!in.isDefinedAt(p)) - assert(false, "Invalid successor for: " + point + " successor " + p + " does not exist") -// if (!p.exceptionHandlerHeader) { -// println("lubbing " + p.predecessors + " outs: " + p.predecessors.map(out.apply).mkString("\n", "\n", "")) - in(p) = lattice.lub(in(p) :: (p.predecessors map out.apply), p.exceptionHandlerStart) -// } + val updated = lattice.lub(in(p) :: (p.predecessors map out.apply), p.exceptionHandlerStart) + if(updated != in(p)) { + in(p) = updated + if (!worklist(p)) { worklist += p; } + } } } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala index 6421d6c8ef..877c51ebc1 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -127,34 +127,6 @@ abstract class TypeFlowAnalysis { } } - /** reinitialize the analysis, keeping around solutions from a previous run. */ - def reinit(m: icodes.IMethod) { - if (this.method == null || this.method.symbol != m.symbol) - init(m) - else reinit { - m foreachBlock { b => - if (!in.contains(b)) { - for (p <- b.predecessors) { - if (out.isDefinedAt(p)) { - in(b) = out(p) - worklist += p - } - /* else - in(b) = typeFlowLattice.bottom - */ } - out(b) = typeFlowLattice.bottom - } - } - for (handler <- m.exh) { - val start = handler.startBlock - if (!in.contains(start)) { - worklist += start - in(start) = lattice.IState(in(start).vars, typeStackLattice.exceptionHandlerStack) - } - } - } - } - def this(m: icodes.IMethod) { this() init(m) @@ -162,7 +134,7 @@ abstract class TypeFlowAnalysis { def run = { timer.start -// icodes.lubs0 = 0 + // icodes.lubs0 = 0 forwardAnalysis(blockTransfer) val t = timer.stop if (settings.debug.value) { @@ -170,216 +142,35 @@ abstract class TypeFlowAnalysis { assert(visited.contains(b), "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? .." + visited)); } -// log("" + method.symbol.fullName + " [" + method.code.blocks.size + " blocks] " -// + "\n\t" + iterations + " iterations: " + t + " ms." -// + "\n\tlubs: " + typeFlowLattice.lubs + " out of which " + icodes.lubs0 + " typer lubs") + // log("" + method.symbol.fullName + " [" + method.code.blocks.size + " blocks] " + // + "\n\t" + iterations + " iterations: " + t + " ms." + // + "\n\tlubs: " + typeFlowLattice.lubs + " out of which " + icodes.lubs0 + " typer lubs") } def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { - b.iterator.foldLeft(in)(interpret) - } - /** The flow function of a given basic block. */ - /* var flowFun: immutable.Map[BasicBlock, TransferFunction] = new immutable.HashMap */ - - /** Fill flowFun with a transfer function per basic block. */ -/* - private def buildFlowFunctions(blocks: List[BasicBlock]) { - def transfer(b: BasicBlock): TransferFunction = { - var gens: List[Gen] = Nil - var consumed: Int = 0 - val stack = new SimulatedStack - - for (instr <- b) instr match { - case THIS(clasz) => - stack push toTypeKind(clasz.tpe) - - case CONSTANT(const) => - stack push toTypeKind(const.tpe) - - case LOAD_ARRAY_ITEM(kind) => - stack.pop2 - stack.push(kind) - - case LOAD_LOCAL(local) => - val t = bindings(local) - stack push (if (t == typeLattice.bottom) local.kind else t) - - case LOAD_FIELD(field, isStatic) => - if (!isStatic) - stack.pop - stack push toTypeKind(field.tpe) - - case LOAD_MODULE(module) => - stack push toTypeKind(module.tpe) - - case STORE_ARRAY_ITEM(kind) => - stack.pop3 - - case STORE_LOCAL(local) => - val t = stack.pop - bindings += (local -> t) - - case STORE_THIS(_) => - stack.pop - - case STORE_FIELD(field, isStatic) => - if (isStatic) - stack.pop - else - stack.pop2 - - case CALL_PRIMITIVE(primitive) => - primitive match { - case Negation(kind) => - stack.pop; stack.push(kind) - case Test(_, kind, zero) => - stack.pop - if (!zero) stack.pop - stack push BOOL; - case Comparison(_, _) => - stack.pop2 - stack push INT - - case Arithmetic(op, kind) => - stack.pop - if (op != NOT) - stack.pop - val k = kind match { - case BYTE | SHORT | CHAR => INT - case _ => kind - } - stack push k - - case Logical(op, kind) => - stack.pop2 - stack push kind - - case Shift(op, kind) => - stack.pop2 - stack push kind - - case Conversion(src, dst) => - stack.pop - stack push dst - - case ArrayLength(kind) => - stack.pop - stack push INT - - case StartConcat => - stack.push(ConcatClass) - - case EndConcat => - stack.pop - stack.push(STRING) - - case StringConcat(el) => - stack.pop2 - stack push ConcatClass - } - - case CALL_METHOD(method, style) => style match { - case Dynamic => - stack.pop(1 + method.info.paramTypes.length) - stack.push(toTypeKind(method.info.resultType)) - - case Static(onInstance) => - if (onInstance) { - stack.pop(1 + method.info.paramTypes.length) - if (!method.isConstructor) - stack.push(toTypeKind(method.info.resultType)); - } else { - stack.pop(method.info.paramTypes.length) - stack.push(toTypeKind(method.info.resultType)) - } - - case SuperCall(mix) => - stack.pop(1 + method.info.paramTypes.length) - stack.push(toTypeKind(method.info.resultType)) - } - - case BOX(kind) => - stack.pop - stack.push(BOXED(kind)) - - case UNBOX(kind) => - stack.pop - stack.push(kind) - - case NEW(kind) => - stack.push(kind) - - case CREATE_ARRAY(elem, dims) => - stack.pop(dims) - stack.push(ARRAY(elem)) - - case IS_INSTANCE(tpe) => - stack.pop - stack.push(BOOL) - - case CHECK_CAST(tpe) => - stack.pop - stack.push(tpe) - - case SWITCH(tags, labels) => - stack.pop - - case JUMP(whereto) => - () - - case CJUMP(success, failure, cond, kind) => - stack.pop2 - - case CZJUMP(success, failure, cond, kind) => - stack.pop - - case RETURN(kind) => - if (kind != UNIT) - stack.pop; - - case THROW() => - stack.pop - - case DROP(kind) => - stack.pop - - case DUP(kind) => - stack.push(stack.head) - - case MONITOR_ENTER() => - stack.pop - - case MONITOR_EXIT() => - stack.pop - - case SCOPE_ENTER(_) | SCOPE_EXIT(_) => - () - - case LOAD_EXCEPTION(_) => - stack.pop(stack.length) - stack.push(typeLattice.Object) - - case _ => - dumpClassesAndAbort("Unknown instruction: " + i) - } - - new TransferFunction(consumed, gens) - } - - for (b <- blocks) { - flowFun = flowFun + (b -> transfer(b)) + var result = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) + var instrs = b.toList + while(!instrs.isEmpty) { + val i = instrs.head + result = mutatingInterpret(result, i) + instrs = instrs.tail } + result } -*/ + /** Abstract interpretation for one instruction. */ def interpret(in: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = { val out = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) + mutatingInterpret(out, i) + } + + def mutatingInterpret(out: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = { val bindings = out.vars val stack = out.stack if (settings.debug.value) { -// Console.println("[before] Stack: " + stack); -// Console.println(i); + // Console.println("[before] Stack: " + stack); + // Console.println(i); } i match { @@ -619,11 +410,292 @@ abstract class TypeFlowAnalysis { } } + case class CallsiteInfo(bb: icodes.BasicBlock, receiver: Symbol, stackLength: Int, concreteMethod: Symbol) + + /** + + A full type-flow analysis on a method computes in- and out-flows for each basic block (that's what MethodTFA does). + + For the purposes of Inliner, doing so guarantees that an abstract typestack-slot is available by the time an inlining candidate (a CALL_METHOD instruction) is visited. + This subclass (MTFAGrowable) of MethodTFA also aims at performing such analysis on CALL_METHOD instructions, with some differences: + + (a) early screening is performed while the type-flow is being computed (in an override of `blockTransfer`) by testing a subset of the conditions that Inliner checks later. + The reasoning here is: if the early check fails at some iteration, there's no chance a follow-up iteration (with a yet more lub-ed typestack-slot) will succeed. + Failure is sufficient to remove that particular CALL_METHOD from the typeflow's `remainingCALLs`. + A forward note: in case inlining occurs at some basic block B, all blocks reachable from B get their CALL_METHOD instructions considered again as candidates + (because of the more precise types that -- perhaps -- can be computed). + + (b) in case the early check does not fail, no conclusive decision can be made, thus the CALL_METHOD stays `isOnwatchlist`. + + In other words, `remainingCALLs` tracks those callsites that still remain as candidates for inlining, so that Inliner can focus on those. + `remainingCALLs` also caches info about the typestack just before the callsite, so as to spare computing them again at inlining time. + + Besides caching, a further optimization involves skipping those basic blocks whose in-flow and out-flow isn't needed anyway (as explained next). + A basic block lacking a callsite in `remainingCALLs`, when visisted by the standard algorithm, won't cause any inlining. + But as we know from the way type-flows are computed, computing the in- and out-flow for a basic block relies in general on those of other basic blocks. + In detail, we want to focus on that sub-graph of the CFG such that control flow may reach a remaining candidate callsite. + Those basic blocks not in that subgraph can be skipped altogether. That's why: + - `forwardAnalysis()` in `MTFAGrowable` now checks for inclusion of a basic block in `relevantBBs` + - same check is performed before adding a block to the worklist, and as part of choosing successors. + The bookkeeping supporting on-the-fly pruning of irrelevant blocks requires overridding most methods of the dataflow-analysis. + + The rest of the story takes place in Inliner, which does not visit all of the method's basic blocks but only on those represented in `remainingCALLs`. + + @author Miguel Garcia, http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/ + + */ class MTFAGrowable extends MethodTFA { import icodes._ - /** discards what must be discarded, blanks what needs to be blanked out, and keeps the rest. */ + val remainingCALLs = mutable.Map.empty[opcodes.CALL_METHOD, CallsiteInfo] + + val preCandidates = mutable.Set.empty[BasicBlock] + + var callerLin: Traversable[BasicBlock] = null + + override def run { + + timer.start + forwardAnalysis(blockTransfer) + val t = timer.stop + + /* Now that `forwardAnalysis(blockTransfer)` has finished, all inlining candidates can be found in `remainingCALLs`, + whose keys are callsites and whose values are pieces of information about the typestack just before the callsite in question. + In order to keep `analyzeMethod()` simple, we collect in `preCandidates` those basic blocks containing at least one candidate. */ + preCandidates.clear() + for(rc <- remainingCALLs) { + preCandidates += rc._2.bb + } + + if (settings.debug.value) { + for(b <- callerLin; if (b != method.startBlock) && preCandidates(b)) { + assert(visited.contains(b), + "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? .." + visited) + } + } + + } + + var shrinkedWatchlist = false + + /* + This is the method where information cached elsewhere is put to use. References are given those other places that populate those caches. + + The goal is avoiding computing type-flows for blocks we don't need (ie blocks not tracked in `relevantBBs`). The method used to add to `relevantBBs` is `putOnRadar`. + + Moreover, it's often the case that the last CALL_METHOD of interest ("of interest" equates to "being tracked in `isOnWatchlist`) isn't the last instruction on the block. + There are cases where the typeflows computed past this `lastInstruction` are needed, and cases when they aren't. + The reasoning behind this decsision is described in `populatePerimeter()`. All `blockTransfer()` needs to do (in order to know at which instruction it can stop) + is querying `isOnPerimeter`. + + Upon visiting a CALL_METHOD that's an inlining candidate, the relevant pieces of information about the pre-instruction typestack are collected for future use. + That is, unless the candidacy test fails. The reasoning here is: if such early check fails at some iteration, there's no chance a follow-up iteration + (with a yet more lub-ed typestack-slot) will succeed. In case of failure we can safely remove the CALL_METHOD from both `isOnWatchlist` and `remainingCALLs`. + + */ + override def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { + var result = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) + + val stopAt = if(isOnPerimeter(b)) lastInstruction(b) else null; + var isPastLast = false + + var instrs = b.toList + while(!isPastLast && !instrs.isEmpty) { + val i = instrs.head + + if(isOnWatchlist(i)) { + val cm = i.asInstanceOf[opcodes.CALL_METHOD] + val msym = cm.method + val paramsLength = msym.info.paramTypes.size + val receiver = result.stack.types.drop(paramsLength).head match { + case REFERENCE(s) => s + case _ => NoSymbol // e.g. the scrutinee is BOX(s) or ARRAY + } + val concreteMethod = inliner.lookupImplFor(msym, receiver) + val isCandidate = { + ( inliner.isClosureClass(receiver) || concreteMethod.isEffectivelyFinal || receiver.isEffectivelyFinal ) && + !blackballed(concreteMethod) + } + if(isCandidate) { + remainingCALLs += Pair(cm, CallsiteInfo(b, receiver, result.stack.length, concreteMethod)) + } else { + remainingCALLs.remove(cm) + isOnWatchlist.remove(cm) + shrinkedWatchlist = true + } + } + + isPastLast = (i eq stopAt) + + if(!isPastLast) { + result = mutatingInterpret(result, i) + instrs = instrs.tail + } + } + + result + } // end of method blockTransfer + + val isOnWatchlist = mutable.Set.empty[Instruction] + + /* Each time CallerCalleeInfo.isSafeToInline determines a concrete callee is unsafe to inline in the current caller, + the fact is recorded in this TFA instance for the purpose of avoiding devoting processing to that callsite next time. + The condition of "being unsafe to inline in the current caller" sticks across inlinings and TFA re-inits + because it depends on the instructions of the callee, which stay unchanged during the course of `analyzeInc(caller)` + (with the caveat of the side-effecting `makePublic` in `helperIsSafeToInline`).*/ + val knownUnsafe = mutable.Set.empty[Symbol] + val knownSafe = mutable.Set.empty[Symbol] + val knownNever = mutable.Set.empty[Symbol] // `knownNever` needs be cleared only at the very end of the inlining phase (unlike `knownUnsafe` and `knownSafe`) + @inline final def blackballed(msym: Symbol): Boolean = { knownUnsafe(msym) || knownNever(msym) } + + val relevantBBs = mutable.Set.empty[BasicBlock] + + private def isPreCandidate(cm: opcodes.CALL_METHOD): Boolean = { + val msym = cm.method + val style = cm.style + // Dynamic == normal invocations + // Static(true) == calls to private members + !msym.isConstructor && !blackballed(msym) && + (style.isDynamic || (style.hasInstance && style.isStatic)) + // && !(msym hasAnnotation definitions.ScalaNoInlineClass) + } + + override def init(m: icodes.IMethod) { + super.init(m) + remainingCALLs.clear() + knownUnsafe.clear() + knownSafe.clear() + // initially populate the watchlist with all callsites standing a chance of being inlined + isOnWatchlist.clear() + relevantBBs.clear() + /* TODO Do we want to perform inlining in non-finally exception handlers? + * Seems counterproductive (the larger the method the less likely it will be JITed. + * It's not that putting on radar only `linearizer linearizeAt (m, m.startBlock)` makes for much shorter inlining times (a minor speedup nonetheless) + * but the effect on method size could be explored. */ + putOnRadar(m.linearizedBlocks(linearizer)) + populatePerimeter() + assert(relevantBBs.isEmpty || relevantBBs.contains(m.startBlock), "you gave me dead code") + } + + def conclusives(b: BasicBlock): List[opcodes.CALL_METHOD] = { + knownBeforehand(b) filter { cm => inliner.isMonadicMethod(cm.method) || inliner.hasInline(cm.method) } + } + + def knownBeforehand(b: BasicBlock): List[opcodes.CALL_METHOD] = { + b.toList collect { case c : opcodes.CALL_METHOD => c } filter { cm => isPreCandidate(cm) && isReceiverKnown(cm) } + } + + private def isReceiverKnown(cm: opcodes.CALL_METHOD): Boolean = { + cm.method.isEffectivelyFinal && cm.method.owner.isEffectivelyFinal + } + + private def putOnRadar(blocks: Traversable[BasicBlock]) { + for(bb <- blocks) { + val preCands = bb.toList collect { + case cm : opcodes.CALL_METHOD + if isPreCandidate(cm) /* && !isReceiverKnown(cm) */ + => cm + } + isOnWatchlist ++= preCands + } + relevantBBs ++= blocks + } + + /* the argument is also included in the result */ + private def transitivePreds(b: BasicBlock): Set[BasicBlock] = { transitivePreds(List(b)) } + + /* those BBs in the argument are also included in the result */ + private def transitivePreds(starters: Traversable[BasicBlock]): Set[BasicBlock] = { + val result = mutable.Set.empty[BasicBlock] + var toVisit: List[BasicBlock] = starters.toList.distinct + while(toVisit.nonEmpty) { + val h = toVisit.head + toVisit = toVisit.tail + result += h + for(p <- h.predecessors; if !result(p) && !toVisit.contains(p)) { toVisit = p :: toVisit } + } + result.toSet + } + + /* those BBs in the argument are also included in the result */ + private def transitiveSuccs(starters: Traversable[BasicBlock]): Set[BasicBlock] = { + val result = mutable.Set.empty[BasicBlock] + var toVisit: List[BasicBlock] = starters.toList.distinct + while(toVisit.nonEmpty) { + val h = toVisit.head + toVisit = toVisit.tail + result += h + for(p <- h.successors; if !result(p) && !toVisit.contains(p)) { toVisit = p :: toVisit } + } + result.toSet + } + + /* A basic block B is "on the perimeter" of the current control-flow subgraph if none of its successors belongs to that subgraph. + * In that case, for the purposes of inlining, we're interested in the typestack right before the last inline candidate in B, not in those afterwards. + * In particular we can do without computing the outflow at B. */ + private def populatePerimeter() { + isOnPerimeter.clear() + var done = true + do { + val (frontier, toPrune) = (relevantBBs filter hasNoRelevantSuccs) partition isWatching + isOnPerimeter ++= frontier + relevantBBs --= toPrune + done = toPrune.isEmpty + } while(!done) + + lastInstruction.clear() + for(b <- isOnPerimeter; val lastIns = b.toList.reverse find isOnWatchlist) { + lastInstruction += (b -> lastIns.get.asInstanceOf[opcodes.CALL_METHOD]) + } + + // assertion: "no relevant block can have a predecessor that is on perimeter" + assert((for (b <- relevantBBs; if transitivePreds(b.predecessors) exists isOnPerimeter) yield b).isEmpty) + } + + private val isOnPerimeter = mutable.Set.empty[BasicBlock] + private val lastInstruction = mutable.Map.empty[BasicBlock, opcodes.CALL_METHOD] + + def hasNoRelevantSuccs(x: BasicBlock): Boolean = { !(x.successors exists relevantBBs) } + + def isWatching(x: BasicBlock): Boolean = (x.toList exists isOnWatchlist) + + + + + /** + + This method is invoked after one or more inlinings have been performed in basic blocks whose in-flow is non-bottom (this makes a difference later). + What we know about those inlinings is given by: + + - `staleOut`: These are the blocks where a callsite was inlined. + For each callsite, all instructions in that block before the callsite were left in the block, and the rest moved to an `afterBlock`. + The out-flow of these basic blocks is thus in general stale, that's why we'll add them to the TFA worklist. + + - `inlined` : These blocks were spliced into the method's CFG as part of inlining. Being new blocks, they haven't been visited yet by the typeflow analysis. + + - `staleIn` : These blocks are what `doInline()` calls `afterBlock`s, ie the new home for instructions that previously appearead + after a callsite in a `staleOut` block. + + Based on the above information, we have to bring up-to-date the caches that `forwardAnalysis` and `blockTransfer` use to skip blocks and instructions. + Those caches are `relevantBBs` and `isOnPerimeter` (for blocks) and `isOnWatchlist` and `lastInstruction` (for CALL_METHODs). + Please notice that all `inlined` and `staleIn` blocks are reachable from `staleOut` blocks. + + The update takes place in two steps: + + (1) `staleOut foreach { so => putOnRadar(linearizer linearizeAt (m, so)) }` + This results in initial populations for `relevantBBs` and `isOnWatchlist`. + Because of the way `isPreCandidate` reuses previous decision-outcomes that are still valid, + this already prunes some candidates standing no chance of being inlined. + + (2) `populatePerimeter()` + Based on the CFG-subgraph determined in (1) as reflected in `relevantBBs`, + this method detects some blocks whose typeflows aren't needed past a certain CALL_METHOD + (not needed because none of its successors is relevant for the purposes of inlining, see `hasNoRelevantSuccs`). + The blocks thus chosen are said to be "on the perimeter" of the CFG-subgraph. + For each of them, its `lastInstruction` (after which no more typeflows are needed) is found. + + */ def reinit(m: icodes.IMethod, staleOut: List[BasicBlock], inlined: collection.Set[BasicBlock], staleIn: collection.Set[BasicBlock]) { if (this.method == null || this.method.symbol != m.symbol) { init(m) @@ -633,31 +705,102 @@ abstract class TypeFlowAnalysis { return; } - reinit { - // asserts conveying an idea what CFG shapes arrive here. - // staleIn foreach (p => assert( !in.isDefinedAt(p), p)) - // staleIn foreach (p => assert(!out.isDefinedAt(p), p)) - // inlined foreach (p => assert( !in.isDefinedAt(p), p)) - // inlined foreach (p => assert(!out.isDefinedAt(p), p)) - // inlined foreach (p => assert(!p.successors.isEmpty || p.lastInstruction.isInstanceOf[icodes.opcodes.THROW], p)) - // staleOut foreach (p => assert( in.isDefinedAt(p), p)) - - // never rewrite in(m.startBlock) - staleOut foreach { b => - if(!inlined.contains(b)) { worklist += b } - out(b) = typeFlowLattice.bottom - } - // nothing else is added to the worklist, bb's reachable via succs will be tfa'ed - blankOut(inlined) - blankOut(staleIn) - // no need to add startBlocks from m.exh + worklist.clear // calling reinit(f: => Unit) would also clear visited, thus forgetting about blocks visited before reinit. + + // asserts conveying an idea what CFG shapes arrive here: + // staleIn foreach (p => assert( !in.isDefinedAt(p), p)) + // staleIn foreach (p => assert(!out.isDefinedAt(p), p)) + // inlined foreach (p => assert( !in.isDefinedAt(p), p)) + // inlined foreach (p => assert(!out.isDefinedAt(p), p)) + // inlined foreach (p => assert(!p.successors.isEmpty || p.lastInstruction.isInstanceOf[icodes.opcodes.THROW], p)) + // staleOut foreach (p => assert( in.isDefinedAt(p), p)) + + // remainingCALLs.clear() + isOnWatchlist.clear() + relevantBBs.clear() + + // never rewrite in(m.startBlock) + staleOut foreach { b => + enqueue(b) + out(b) = typeFlowLattice.bottom } + // nothing else is added to the worklist, bb's reachable via succs will be tfa'ed + blankOut(inlined) + blankOut(staleIn) + // no need to add startBlocks from m.exh + + staleOut foreach { so => putOnRadar(linearizer linearizeAt (m, so)) } + populatePerimeter() + + } // end of method reinit + + /* this is not a general purpose method to add to the worklist, + * because the assert is expected to hold only when called from MTFAGrowable.reinit() */ + private def enqueue(b: BasicBlock) { + assert(in(b) ne typeFlowLattice.bottom) + if(!worklist.contains(b)) { worklist += b } + } + + /* this is not a general purpose method to add to the worklist, + * because the assert is expected to hold only when called from MTFAGrowable.reinit() */ + private def enqueue(bs: Traversable[BasicBlock]) { + bs foreach enqueue } private def blankOut(blocks: collection.Set[BasicBlock]) { blocks foreach { b => - in(b) = typeFlowLattice.bottom - out(b) = typeFlowLattice.bottom + in(b) = typeFlowLattice.bottom + out(b) = typeFlowLattice.bottom + } + } + + /* + This is basically the plain-old forward-analysis part of a dataflow algorithm, + adapted to skip non-relevant blocks (as determined by `reinit()` via `populatePerimeter()`). + + The adaptations are: + + - only relevant blocks dequeued from the worklist move on to have the transfer function applied + + - `visited` now means the transfer function was applied to the block, + but please notice that this does not imply anymore its out-flow to be different from bottom, + because a block on the perimeter will have per-instruction typeflows computed only up to its `lastInstruction`. + In case you need to know whether a visted block `v` has been "fully visited", evaluate `out(v) ne typeflowLattice.bottom` + + - given that the transfer function may remove callsite-candidates from the watchlist (thus, they are not candidates anymore) + there's an opportunity to detect whether a previously relevant block has been left without candidates. + That's what `shrinkedWatchlist` detects. Provided the block was on the perimeter, we know we can skip it from now now, + and we can also constrain the CFG-subgraph by finding a new perimeter (thus the invocation to `populatePerimeter()`). + */ + override def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = { + while (!worklist.isEmpty && relevantBBs.nonEmpty) { + if (stat) iterations += 1 + val point = worklist.iterator.next; worklist -= point; + if(relevantBBs(point)) { + shrinkedWatchlist = false + val output = f(point, in(point)) + visited += point; + if(isOnPerimeter(point)) { + if(shrinkedWatchlist && !isWatching(point)) { + relevantBBs -= point; + populatePerimeter() + } + } else { + val propagate = ((lattice.bottom == out(point)) || output != out(point)) + if (propagate) { + out(point) = output + val succs = point.successors filter relevantBBs + succs foreach { p => + assert((p.predecessors filter isOnPerimeter).isEmpty) + val updated = lattice.lub(List(output, in(p)), p.exceptionHandlerStart) + if(updated != in(p)) { + in(p) = updated + enqueue(p) + } + } + } + } + } } } diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 66f802f74f..3d7f08cebe 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -38,6 +38,33 @@ abstract class Inliners extends SubComponent { res } + /** Look up implementation of method 'sym in 'clazz'. + */ + def lookupImplFor(sym: Symbol, clazz: Symbol): Symbol = { + // TODO: verify that clazz.superClass is equivalent here to clazz.tpe.parents(0).typeSymbol (.tpe vs .info) + def needsLookup = ( + (clazz != NoSymbol) + && (clazz != sym.owner) + && !sym.isEffectivelyFinal + && clazz.isEffectivelyFinal + ) + def lookup(clazz: Symbol): Symbol = { + // println("\t\tlooking up " + meth + " in " + clazz.fullName + " meth.owner = " + meth.owner) + if (sym.owner == clazz || isBottomType(clazz)) sym + else sym.overridingSymbol(clazz) match { + case NoSymbol => if (sym.owner.isTrait) sym else lookup(clazz.superClass) + case imp => imp + } + } + if (needsLookup) { + val concreteMethod = lookup(clazz) + debuglog("\tlooked up method: " + concreteMethod.fullName) + + concreteMethod + } + else sym + } + /* A warning threshold */ private final val MAX_INLINE_MILLIS = 2000 @@ -67,8 +94,7 @@ abstract class Inliners extends SubComponent { try { super.run() } finally { - inliner.NonPublicRefs.usesNonPublics.clear() - inliner.recentTFAs.clear + inliner.clearCaches() } } } @@ -80,6 +106,21 @@ abstract class Inliners extends SubComponent { def isClosureClass(cls: Symbol): Boolean = cls.isFinal && cls.isSynthetic && !cls.isModuleClass && cls.isAnonymousFunction + /* + TODO now that Inliner runs faster we could consider additional "monadic methods" (in the limit, all those taking a closure as last arg) + Any "monadic method" occurring in a given caller C that is not `isMonadicMethod()` will prevent CloseElim from eliminating + any anonymous-closure-class any whose instances are given as argument to C invocations. + */ + def isMonadicMethod(sym: Symbol) = { + nme.unspecializedName(sym.name) match { + case nme.foreach | nme.filter | nme.withFilter | nme.map | nme.flatMap => true + case _ => false + } + } + + def hasInline(sym: Symbol) = sym hasAnnotation ScalaInlineClass + def hasNoInline(sym: Symbol) = sym hasAnnotation ScalaNoInlineClass + /** * Simple inliner. */ @@ -92,9 +133,6 @@ abstract class Inliners extends SubComponent { } import NonPublicRefs._ - private def hasInline(sym: Symbol) = sym hasAnnotation ScalaInlineClass - private def hasNoInline(sym: Symbol) = sym hasAnnotation ScalaNoInlineClass - /** The current iclass */ private var currentIClazz: IClass = _ private def warn(pos: Position, msg: String) = currentIClazz.cunit.warning(pos, msg) @@ -121,6 +159,21 @@ abstract class Inliners extends SubComponent { (hasRETURN, a) } + def clearCaches() { + // methods + NonPublicRefs.usesNonPublics.clear() + recentTFAs.clear + tfa.knownUnsafe.clear() + tfa.knownSafe.clear() + tfa.knownNever.clear() + // basic blocks + tfa.preCandidates.clear() + tfa.relevantBBs.clear() + // callsites + tfa.remainingCALLs.clear() + tfa.isOnWatchlist.clear() + } + def analyzeClass(cls: IClass): Unit = if (settings.inline.value) { debuglog("Analyzing " + cls) @@ -142,7 +195,38 @@ abstract class Inliners extends SubComponent { val splicedBlocks = mutable.Set.empty[BasicBlock] val staleIn = mutable.Set.empty[BasicBlock] + /** + * A transformation local to the body of the argument. + * An linining decision consists in replacing a callsite with the body of the callee. + * Please notice that, because `analyzeMethod()` itself may modify a method body, + * the particular callee bodies that end up being inlined depend on the particular order in which methods are visited + * (no topological ordering over the call-graph is attempted). + * + * Making an inlining decision requires type-flow information for both caller and callee. + * Regarding the caller, such information is needed only for basic blocks containing inlining candidates + * (and their transitive predecessors). This observation leads to using a custom type-flow analysis (MTFAGrowable) + * that can be re-inited, i.e. that reuses lattice elements (type-flow information) computed in a previous iteration + * as starting point for faster convergence in a new iteration. + * + * The mechanics of inlining are iterative for a given invocation of `analyzeMethod(m)`, + * thus considering the basic blocks that successful inlining added in a previous iteration: + * + * (1) before the iterations proper start, so-called preinlining is performed. + * Those callsites whose (receiver, concreteMethod) are both known statically + * can be analyzed for inlining before computing a type-flow. Details in `preInline()` + * + * (2) the first iteration computes type-flow information for basic blocks containing inlining candidates + * (and their transitive predecessors), so called `relevantBBs`. + * The ensuing analysis of each candidate (performed by `analyzeInc()`) + * may result in a CFG isomorphic to that of the callee being inserted where the callsite was + * (i.e. a CALL_METHOD instruction is replaced with a single-entry single-exit CFG, which we call "successful inlining"). + * + * (3) following iterations have their relevant basic blocks updated to focus + * on the inlined basic blocks and their successors only. Details in `MTFAGrowable.reinit()` + * */ def analyzeMethod(m: IMethod): Unit = { + // m.normalize + var sizeBeforeInlining = m.code.blockCount var instrBeforeInlining = m.code.instructionCount var retry = false @@ -154,17 +238,53 @@ abstract class Inliners extends SubComponent { val inlinedMethodCount = mutable.HashMap.empty[Symbol, Int] withDefaultValue 0 val caller = new IMethodInfo(m) - var info: tfa.lattice.Elem = null - def analyzeInc(msym: Symbol, i: Instruction, bb: BasicBlock): Boolean = { - var inlined = false - def paramTypes = msym.info.paramTypes - val receiver = (info.stack.types drop paramTypes.length) match { - case Nil => log("analyzeInc(" + msym + "), no type on the stack!") ; NoSymbol - case REFERENCE(s) :: _ => s - case _ => NoSymbol + def preInline(isFirstRound: Boolean): Int = { + val inputBlocks = caller.m.linearizedBlocks() + val callsites: Function1[BasicBlock, List[opcodes.CALL_METHOD]] = { + if(isFirstRound) tfa.conclusives else tfa.knownBeforehand } - val concreteMethod = lookupImplFor(msym, receiver) + inlineWithoutTFA(inputBlocks, callsites) + } + + /** + * Inline straightforward callsites (those that can be inlined without a TFA). + * + * To perform inlining, all we need to know is listed as formal params in `analyzeInc()`: + * - callsite and block containing it + * - actual (ie runtime) class of the receiver + * - actual (ie runtime) method being invoked + * - stack length just before the callsite (to check whether enough arguments have been pushed). + * The assert below lists the conditions under which "no TFA is needed" + * (the statically known receiver and method are both final, thus, at runtime they can't be any others than those). + * + */ + def inlineWithoutTFA(inputBlocks: Traversable[BasicBlock], callsites: Function1[BasicBlock, List[opcodes.CALL_METHOD]]): Int = { + var inlineCount = 0 + import scala.util.control.Breaks._ + for(x <- inputBlocks; val easyCake = callsites(x); if easyCake.nonEmpty) { + breakable { + for(ocm <- easyCake) { + assert(ocm.method.isEffectivelyFinal && ocm.method.owner.isEffectivelyFinal) + if(analyzeInc(ocm, x, ocm.method.owner, -1, ocm.method)) { + inlineCount += 1 + break + } + } + } + } + + inlineCount + } + + /** + Decides whether it's feasible and desirable to inline the body of the method given by `concreteMethod` + at the program point given by `i` (a callsite). The boolean result indicates whether inlining was performed. + + */ + def analyzeInc(i: CALL_METHOD, bb: BasicBlock, receiver: Symbol, stackLength: Int, concreteMethod: Symbol): Boolean = { + var inlined = false + val msym = i.method def warnNoInline(reason: String) = { if (hasInline(msym) && !caller.isBridge) @@ -209,7 +329,7 @@ abstract class Inliners extends SubComponent { val inc = new IMethodInfo(callee) val pair = new CallerCalleeInfo(caller, inc, fresh, inlinedMethodCount) - if (pair isStampedForInlining info.stack) { + if (pair isStampedForInlining stackLength) { retry = true inlined = true if (isCountable) @@ -228,9 +348,9 @@ abstract class Inliners extends SubComponent { } else { if (settings.debug.value) - pair logFailure info.stack + pair logFailure stackLength - warnNoInline(pair failureReason info.stack) + warnNoInline(pair failureReason stackLength) } case None => warnNoInline("bytecode was not available") @@ -241,38 +361,96 @@ abstract class Inliners extends SubComponent { if (!isAvailable) "bytecode was not available" else "it can be overridden" ) + inlined } - import scala.util.control.Breaks._ + /* Pre-inlining consists in invoking the usual inlining subroutine with (receiver class, concrete method) pairs as input + * where both method and receiver are final, which implies that the receiver computed via TFA will always match `concreteMethod.owner`. + * + * As with any invocation of `analyzeInc()` the inlining outcome is based on heuristics which favor inlining an isMonadicMethod before other methods. + * That's why preInline() is invoked twice: any inlinings downplayed by the heuristics during the first round get an opportunity to rank higher during the second. + * + * As a whole, both `preInline()` invocations amount to priming the inlining process, + * so that the first TFA run afterwards is able to gain more information as compared to a cold-start. + */ + val totalPreInlines = { + val firstRound = preInline(true) + if(firstRound == 0) 0 else (firstRound + preInline(false)) + } + staleOut.clear() + splicedBlocks.clear() + staleIn.clear() + do { retry = false log("Analyzing " + m + " count " + count + " with " + caller.length + " blocks") + + /* it's important not to inline in unreachable basic blocks. linearizedBlocks() returns only reachable ones. */ + tfa.callerLin = caller.m.linearizedBlocks() + /* TODO Do we want to perform inlining in non-finally exception handlers? + * Seems counterproductive (the larger the method the less likely it will be JITed). + * The alternative above would be `linearizer.linearizeAt(caller.m, caller.m.startBlock)`. + * See also comment on the same topic in TypeFlowAnalysis. */ + tfa.reinit(m, staleOut.toList, splicedBlocks, staleIn) tfa.run staleOut.clear() splicedBlocks.clear() staleIn.clear() - caller.m.linearizedBlocks() foreach { bb => - info = tfa in bb - + import scala.util.control.Breaks._ + for(bb <- tfa.callerLin; if tfa.preCandidates(bb)) { + val cms = bb.toList collect { case cm : CALL_METHOD => cm } breakable { - for (i <- bb) { - i match { - // Dynamic == normal invocations - // Static(true) == calls to private members - case CALL_METHOD(msym, Dynamic | Static(true)) if !msym.isConstructor => - if (analyzeInc(msym, i, bb)) { - break - } - case _ => () + for (cm <- cms; if tfa.remainingCALLs.isDefinedAt(cm)) { + val analysis.CallsiteInfo(_, receiver, stackLength, concreteMethod) = tfa.remainingCALLs(cm) + if (analyzeInc(cm, bb, receiver, stackLength, concreteMethod)) { + break } - info = tfa.interpret(info, i) } } + } + + /* As part of inlining, some instructions are moved to a new block. + * In detail: the instructions moved to a new block originally appeared after a (by now inlined) callsite. + * Their new home is an `afterBlock` created by `doInline()` to that effect. + * Each block in staleIn is one such `afterBlock`. + * + * Some of those instructions may be CALL_METHOD possibly tracked in `remainingCALLs` + * (with an entry still noting the old containing block). However, that causes no problem: + * + * (1) such callsites won't be analyzed for inlining by `analyzeInc()` (*in this iteration*) + * because of the `break` that abandons the original basic block where it was contained. + * + * (2) Additionally, its new containing block won't be visited either (*in this iteration*) + * because the new blocks don't show up in the linearization computed before inlinings started: + * `for(bb <- tfa.callerLin; if tfa.preCandidates(bb)) {` + * + * For a next iteration, the new home of any instructions that have moved + * will be tracked properly in `remainingCALLs` after `MTFAGrowable.reinit()` puts on radar their new homes. + * + */ + if(retry) { + for(afterBlock <- staleIn) { + val justCALLsAfter = afterBlock.toList collect { case c : opcodes.CALL_METHOD => c } + for(ia <- justCALLsAfter) { tfa.remainingCALLs.remove(ia) } + } + } + /* + if(splicedBlocks.nonEmpty) { // TODO explore (saves time but leads to slightly different inlining decisions) + // opportunistically perform straightforward inlinings before the next typeflow round + val savedRetry = retry + val savedStaleOut = staleOut.toSet; staleOut.clear() + val savedStaleIn = staleIn.toSet ; staleIn.clear() + val howmany = inlineWithoutTFA(splicedBlocks, tfa.knownBeforehand) + splicedBlocks ++= staleIn + staleOut.clear(); staleOut ++= savedStaleOut; + staleIn.clear(); staleIn ++= savedStaleIn; + retry = savedRetry } + */ if (tfa.stat) log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + caller.length + ")") @@ -288,13 +466,6 @@ abstract class Inliners extends SubComponent { } } - private def isMonadicMethod(sym: Symbol) = { - nme.unspecializedName(sym.name) match { - case nme.foreach | nme.filter | nme.withFilter | nme.map | nme.flatMap => true - case _ => false - } - } - private def isHigherOrderMethod(sym: Symbol) = sym.isMethod && atPhase(currentRun.erasurePhase.prev)(sym.info.paramTypes exists isFunctionType) @@ -308,33 +479,6 @@ abstract class Inliners extends SubComponent { res } - /** Look up implementation of method 'sym in 'clazz'. - */ - def lookupImplFor(sym: Symbol, clazz: Symbol): Symbol = { - // TODO: verify that clazz.superClass is equivalent here to clazz.tpe.parents(0).typeSymbol (.tpe vs .info) - def needsLookup = ( - (clazz != NoSymbol) - && (clazz != sym.owner) - && !sym.isEffectivelyFinal - && clazz.isEffectivelyFinal - ) - def lookup(clazz: Symbol): Symbol = { - // println("\t\tlooking up " + meth + " in " + clazz.fullName + " meth.owner = " + meth.owner) - if (sym.owner == clazz || isBottomType(clazz)) sym - else sym.overridingSymbol(clazz) match { - case NoSymbol => if (sym.owner.isTrait) sym else lookup(clazz.superClass) - case imp => imp - } - } - if (needsLookup) { - val concreteMethod = lookup(clazz) - debuglog("\tlooked up method: " + concreteMethod.fullName) - - concreteMethod - } - else sym - } - class IMethodInfo(val m: IMethod) { val sym = m.symbol val name = sym.name @@ -386,10 +530,13 @@ abstract class Inliners extends SubComponent { /** Inline 'inc' into 'caller' at the given block and instruction. * The instruction must be a CALL_METHOD. */ - def doInline(block: BasicBlock, instr: Instruction) { + def doInline(block: BasicBlock, instr: CALL_METHOD) { staleOut += block + tfa.remainingCALLs.remove(instr) // this bookkpeeping is done here and not in MTFAGrowable.reinit due to (1st) convenience and (2nd) necessity. + tfa.isOnWatchlist.remove(instr) // ditto + val targetPos = instr.pos log("Inlining " + inc.m + " in " + caller.m + " at pos: " + posToStr(targetPos)) @@ -557,10 +704,10 @@ abstract class Inliners extends SubComponent { if (settings.debug.value) icodes.checkValid(caller.m) } - def isStampedForInlining(stack: TypeStack) = - !sameSymbols && inc.m.hasCode && shouldInline && isSafeToInline(stack) + def isStampedForInlining(stackLength: Int) = + !sameSymbols && inc.m.hasCode && shouldInline && isSafeToInline(stackLength) - def logFailure(stack: TypeStack) = log( + def logFailure(stackLength: Int) = log( """|inline failed for %s: | pair.sameSymbols: %s | inc.numInlined < 2: %s @@ -569,13 +716,13 @@ abstract class Inliners extends SubComponent { | shouldInline: %s """.stripMargin.format( inc.m, sameSymbols, inlinedMethodCount(inc.sym) < 2, - inc.m.hasCode, isSafeToInline(stack), shouldInline + inc.m.hasCode, isSafeToInline(stackLength), shouldInline ) ) - def failureReason(stack: TypeStack) = + def failureReason(stackLength: Int) = if (!inc.m.hasCode) "bytecode was unavailable" - else if (!isSafeToInline(stack)) "it is unsafe (target may reference private fields)" + else if (!isSafeToInline(stackLength)) "it is unsafe (target may reference private fields)" else "of a bug (run with -Ylog:inline -Ydebug for more information)" def canAccess(level: NonPublicRefs.Value) = level match { @@ -587,15 +734,26 @@ abstract class Inliners extends SubComponent { private def sameOwner = caller.owner == inc.owner /** A method is safe to inline when: - * - it does not contain calls to private methods when - * called from another class + * - it does not contain calls to private methods when called from another class * - it is not inlined into a position with non-empty stack, * while having a top-level finalizer (see liftedTry problem) * - it is not recursive * Note: * - synthetic private members are made public in this pass. */ - def isSafeToInline(stack: TypeStack): Boolean = { + def isSafeToInline(stackLength: Int): Boolean = { + + if(tfa.blackballed(inc.sym)) { return false } + if(tfa.knownSafe(inc.sym)) { return true } + + if(helperIsSafeToInline(stackLength)) { + tfa.knownSafe += inc.sym; true + } else { + tfa.knownUnsafe += inc.sym; false + } + } + + private def helperIsSafeToInline(stackLength: Int): Boolean = { def makePublic(f: Symbol): Boolean = (inc.m.sourceFile ne NoSourceFile) && (f.isSynthetic || f.isParamAccessor) && { debuglog("Making not-private symbol out of synthetic: " + f) @@ -642,9 +800,10 @@ abstract class Inliners extends SubComponent { }) canAccess(accessNeeded) && { - val isIllegalStack = (stack.length > inc.minimumStack && inc.hasNonFinalizerHandler) + val isIllegalStack = (stackLength > inc.minimumStack && inc.hasNonFinalizerHandler) + !isIllegalStack || { - debuglog("method " + inc.sym + " is used on a non-empty stack with finalizer. Stack: " + stack) + debuglog("method " + inc.sym + " is used on a non-empty stack with finalizer.") false } } diff --git a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala index 7f7f7e7b65..252b3ccffc 100644 --- a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala +++ b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala @@ -517,7 +517,7 @@ abstract class ExplicitOuter extends InfoTransform super.transform(treeCopy.Apply(tree, sel, outerVal :: args)) // entry point for pattern matcher translation - case mch: Match => + case mch: Match if (!opt.virtPatmat) => // don't use old pattern matcher as fallback when the user wants the virtualizing one matchTranslation(mch) case _ => diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index ab4a2141a9..841cd4a204 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -228,9 +228,9 @@ abstract class UnCurry extends InfoTransform * case P_1 if G_1 => E_1 * ... * case P_n if G_n => true - * case _ => this.missingCase(x) + * case _ => this.missingCase(expr) * } - * def isDefinedAtCurrent(x: T): boolean = (x: @unchecked) match { + * def _isDefinedAt(x: T): boolean = (x: @unchecked) match { * case P_1 if G_1 => true * ... * case P_n if G_n => true @@ -240,7 +240,7 @@ abstract class UnCurry extends InfoTransform * new $anon() * * However, if one of the patterns P_i if G_i is a default pattern, - * drop the last default clause in tghe definition of `apply` and generate for `isDefinedAtCurrent` instead + * drop the last default clause in the definition of `apply` and generate for `_isDefinedAt` instead * * def isDefinedAtCurrent(x: T): boolean = true */ @@ -291,73 +291,26 @@ abstract class UnCurry extends InfoTransform val substParam = new TreeSymSubstituter(fun.vparams map (_.symbol), params) def substTree[T <: Tree](t: T): T = substParam(resetLocalAttrs(t)) - // waiting here until we can mix case classes and extractors reliably (i.e., when virtpatmat becomes the default) - // object VirtPatmatOpt { - // object Last { - // def unapply[T](xs: List[T]) = xs.lastOption - // } - // // keep this in synch by what's generated by combineCases/runOrElse - // object MatcherBlock { - // def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree])] = matcher match { // TODO: BUG the unapplySeq version of the case below does not seem to work in virtpatmat?? - // case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) => Some(zero, x, matchRes, keepGoing, stats) - // case _ => None - // } - // } - // // TODO: virtpatmat use case: would be nice if could abstract over the repeated pattern more easily - // // case Block(Last(P)) => - // // case P => - // def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree], Tree => Tree)] = matcher match { - // case MatcherBlock(zero, x, matchRes, keepGoing, stats) => Some(zero, x, matchRes, keepGoing, stats, identity[Tree]) - // case Block(outerStats, MatcherBlock(zero, x, matchRes, keepGoing, stats)) => Some(zero, x, matchRes, keepGoing, stats, inner => Block(outerStats, inner)) - // case b => treeBrowser browse b; None - // } - // } - - // TODO: optimize duplication, but make sure ValDef's introduced by wrap are treated correctly - def dupMatch(selector: Tree, cases: List[CaseDef], wrap: Match => Tree = identity) = { - def transformCase(cdef: CaseDef): CaseDef = - CaseDef(cdef.pat, cdef.guard, Literal(Constant(true))) - def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false))) - - gen.mkUncheckedMatch( - if (cases exists treeInfo.isDefaultCase) Literal(Constant(true)) - else substTree(wrap(Match(selector, (cases map transformCase) :+ defaultCase)).duplicate) - ) - } + object isDefinedAtTransformer extends gen.MatchMatcher { + // TODO: optimize duplication, but make sure ValDef's introduced by wrap are treated correctly + override def caseMatch(orig: Tree, selector: Tree, cases: List[CaseDef], wrap: Tree => Tree): Tree = { + def transformCase(cdef: CaseDef): CaseDef = + CaseDef(cdef.pat, cdef.guard, Literal(Constant(true))) - def dupVirtMatch(zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], wrap: Block => Tree = identity) = { - 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 block for the RHS (emitted by pmgen.one), 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) - } + def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false))) + + val casesNoSynthCatchAll = dropSyntheticCatchAll(cases) + + gen.mkUncheckedMatch( + if (casesNoSynthCatchAll exists treeInfo.isDefaultCase) Literal(Constant(true)) + else substTree(wrap(Match(selector, (casesNoSynthCatchAll map transformCase) :+ defaultCase)).duplicate) + ) } - val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList - val idaBlock = wrap(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 - } - DefDef(m, (fun.body: @unchecked) match { - case Match(selector, cases) => - dupMatch(selector, cases) - case Block((vd: ValDef) :: Nil, Match(selector, cases)) => // can't factor this out using an extractor due to bugs in the old pattern matcher - dupMatch(selector, cases, m => Block(List(vd), m)) - // virtpatmat -- TODO: find a better way to keep this in synch with the code generated by patmatvirtualizer - case Apply(Apply(TypeApply(Select(tgt, nme.runOrElse), targs), args_scrut), args_pm) if opt.virtPatmat => + override def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = { object noOne extends Transformer { override val treeCopy = newStrictTreeCopier // must duplicate everything - val one = tgt.tpe member newTermName("one") + val one = _match.tpe member newTermName("one") override def transform(tree: Tree): Tree = tree match { 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 @@ -367,15 +320,34 @@ abstract class UnCurry extends InfoTransform super.transform(tree) } } - substTree(Apply(Apply(TypeApply(Select(tgt.duplicate, tgt.tpe.member(newTermName("isSuccess"))), targs map (_.duplicate)), args_scrut map (_.duplicate)), args_pm map (noOne.transform))) - // for the optimized version of virtpatmat - case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) if opt.virtPatmat => - dupVirtMatch(zero, x, matchRes, keepGoing, stats) - case Block(outerStats, Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _)) if opt.virtPatmat => // can't factor this out using an extractor due to bugs in the old pattern matcher - dupVirtMatch(zero, x, matchRes, keepGoing, stats, m => Block(outerStats, m)) - // case other => - // treeBrowser browse other - }) + substTree(Apply(Apply(TypeApply(Select(_match.duplicate, _match.tpe.member(newTermName("isSuccess"))), targs map (_.duplicate)), List(scrut.duplicate)), List(noOne.transform(matcher)))) + } + + override def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree) = { + 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 block for the RHS (emitted by pmgen.one), except for the assignment to keepGoing + case gen.VirtualCaseDef(assignKeepGoing, matchRes, zero) if assignKeepGoing.lhs.symbol eq keepGoing.symbol => + Block(List(assignKeepGoing), zero) + case _ => + super.transform(tree) + } + } + val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList + val idaBlock = wrap(Block( + zero :: + x :: + /* drop matchRes def */ + keepGoing :: + statsNoMatchRes, + NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` epilogue by `!keepGoing` + )) + substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed + } + } + + DefDef(m, isDefinedAtTransformer(fun.body)) } val members = @@ -679,7 +651,8 @@ abstract class UnCurry extends InfoTransform if (dd.symbol hasAnnotation VarargsClass) addJavaVarargsForwarders(dd, flatdd, tree) flatdd case Try(body, catches, finalizer) => - if (catches forall treeInfo.isCatchCase) tree + if (opt.virtPatmat) { if(catches exists (cd => !treeInfo.isCatchCase(cd))) debugwarn("VPM BUG! illegal try/catch "+ catches); tree } + else if (catches forall treeInfo.isCatchCase) tree else { val exname = unit.freshTermName("ex$") val cases = @@ -701,7 +674,7 @@ abstract class UnCurry extends InfoTransform } debuglog("rewrote try: " + catches + " ==> " + catchall); val catches1 = localTyper.typedCases( - tree, List(catchall), ThrowableClass.tpe, WildcardType) + List(catchall), ThrowableClass.tpe, WildcardType) treeCopy.Try(tree, body, catches1, finalizer) } case Apply(Apply(fn, args), args1) => diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala index 6d31243fd0..25dcc302ce 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala @@ -43,7 +43,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => val outer = newTermName("<outer>") val runOrElse = newTermName("runOrElse") val zero = newTermName("zero") - val __match = newTermName("__match") + val _match = newTermName("__match") // don't call it __match, since that will trigger virtual pattern matching... def counted(str: String, i: Int) = newTermName(str+i) } @@ -51,8 +51,8 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => object MatchTranslator { def apply(typer: Typer): MatchTranslation = { import typer._ - // typing `__match` to decide which MatchTranslator to create adds 4% to quick.comp.timer - newTyper(context.makeImplicit(reportAmbiguousErrors = false)).silent(_.typed(Ident(vpmName.__match), EXPRmode, WildcardType), reportAmbiguousErrors = false) match { + // typing `_match` to decide which MatchTranslator to create adds 4% to quick.comp.timer + newTyper(context.makeImplicit(reportAmbiguousErrors = false)).silent(_.typed(Ident(vpmName._match), EXPRmode, WildcardType), reportAmbiguousErrors = false) match { case SilentResultValue(ms) => new PureMatchTranslator(typer, ms) case _ => new OptimizingMatchTranslator(typer) } @@ -116,6 +116,10 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore => import typer.{typed, context, silent, reallyExists} + private def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match { + case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args) + case _ => tp + } /** Implement a pattern match by turning its cases (including the implicit failure case) * into the corresponding (monadic) extractors, and combining them with the `orElse` combinator. @@ -133,11 +137,6 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // and the only place that emits Matches after typers is for exception handling anyway) assert(phase.id <= currentRun.typerPhase.id, phase) - def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match { - case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args) - case _ => tp - } - val scrutType = repeatedToSeq(elimAnonymousClass(scrut.tpe.widen)) val scrutSym = freshSym(scrut.pos, pureType(scrutType)) @@ -146,6 +145,47 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, matchOwner) } + // return list of typed CaseDefs that are supported by the backend (typed/bind/wildcard) + // we don't have a global scrutinee -- the caught exception must be bound in each of the casedefs + // there's no need to check the scrutinee for null -- "throw null" becomes "throw new NullPointerException" + // try to simplify to a type-based switch, or fall back to a catch-all case that runs a normal pattern match + // unlike translateMatch, we type our result before returning it + def translateTry(caseDefs: List[CaseDef], pt: Type, pos: Position): List[CaseDef] = + // if they're already simple enough to be handled by the back-end, we're done + if (caseDefs forall treeInfo.isCatchCase) caseDefs + else { + val okPt = repeatedToSeq(pt) + val switch = { + val bindersAndCases = caseDefs map { caseDef => + // generate a fresh symbol for each case, hoping we'll end up emitting a type-switch (we don't have a global scrut there) + // if we fail to emit a fine-grained switch, have to do translateCase again with a single scrutSym (TODO: uniformize substitution on treemakers so we can avoid this) + val caseScrutSym = freshSym(pos, pureType(ThrowableClass.tpe)) + (caseScrutSym, propagateSubstitution(translateCase(caseScrutSym, okPt)(caseDef), EmptySubstitution)) + } + + (emitTypeSwitch(bindersAndCases, pt) map (_.map(fixerUpper(matchOwner, pos).apply(_).asInstanceOf[CaseDef]))) + } + + val catches = switch getOrElse { + val scrutSym = freshSym(pos, pureType(ThrowableClass.tpe)) + val casesNoSubstOnly = caseDefs map { caseDef => (propagateSubstitution(translateCase(scrutSym, okPt)(caseDef), EmptySubstitution))} + + val exSym = freshSym(pos, pureType(ThrowableClass.tpe), "ex") + + List( + atPos(pos) { + CaseDef( + Bind(exSym, Ident(nme.WILDCARD)), // TODO: does this need fixing upping? + EmptyTree, + combineCasesNoSubstOnly(CODE.REF(exSym), scrutSym, casesNoSubstOnly, pt, matchOwner, scrut => Throw(CODE.REF(exSym))) + ) + }) + } + + typer.typedCases(catches, ThrowableClass.tpe, WildcardType) + } + + /** The translation of `pat if guard => body` has two aspects: * 1) the substitution due to the variables bound by patterns @@ -668,6 +708,10 @@ class Foo(x: Other) { x._1 } // no error in this order def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = None + // for catch + def emitTypeSwitch(bindersAndCases: List[(Symbol, List[TreeMaker])], pt: Type): Option[List[CaseDef]] = + None + abstract class TreeMaker { /** captures the scope and the value of the bindings in patterns * important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed) @@ -788,6 +832,7 @@ class Foo(x: Other) { x._1 } // no error in this order } // implements the run-time aspects of (ยง8.2) (typedPattern has already done the necessary type transformations) + // TODO: normalize construction, which yields a combination of a EqualityTestTreeMaker (when necessary) and a TypeTestTreeMaker case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends CondTreeMaker { val nextBinderTp = glb(List(patBinder.info.widen, pt)) @@ -843,6 +888,10 @@ class Foo(x: Other) { x._1 } // no error in this order val cond = typeAndEqualityTest(patBinder, pt) val res = codegen._asInstanceOf(patBinder, nextBinderTp) + + // TODO: remove this + def isStraightTypeTest = cond match { case TypeApply(_, _) => cond.symbol == Any_isInstanceOf case _ => false } + override def toString = "TET"+(patBinder, pt) } @@ -926,25 +975,30 @@ class Foo(x: Other) { x._1 } // no error in this order } // calls propagateSubstitution on the treemakers - def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = fixerUpper(owner, scrut.pos){ - val casesUnOpt = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them + def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = { + val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them + combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, CODE.MATCHERROR(_)) + } - emitSwitch(scrut, scrutSym, casesUnOpt, pt).getOrElse{ + def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFail: Tree => Tree): Tree = fixerUpper(owner, scrut.pos){ + emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt).getOrElse{ val (matcher, hasDefault, toHoist) = - if (casesUnOpt nonEmpty) { + if (casesNoSubstOnly nonEmpty) { // when specified, need to propagate pt explicitly (type inferencer can't handle it) val optPt = if (isFullyDefined(pt)) inMatchMonad(pt) else NoType - // do this check on casesUnOpt, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one + // do this check on casesNoSubstOnly, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one // exhaustivity and reachability must be checked before optimization as well - val hasDefault = casesUnOpt.nonEmpty && { - val nonTrivLast = casesUnOpt.last + // TODO: improve, a trivial type test before the body still makes for a default case + // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op) + val hasDefault = casesNoSubstOnly.nonEmpty && { + val nonTrivLast = casesNoSubstOnly.last nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker] } - val (cases, toHoist) = optimizeCases(scrutSym, casesUnOpt, pt) + val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt) val combinedCases = cases.map(combineExtractors(_, pt)).reduceLeft(codegen.typedOrElse(optPt)) @@ -952,7 +1006,11 @@ class Foo(x: Other) { x._1 } // no error in this order (combinedCases, hasDefault, toHoist) } else (codegen.zero, false, Nil) - val expr = codegen.runOrElse(scrut, scrutSym, matcher, if (isFullyDefined(pt)) pt else NoType, hasDefault) + // catch-all + val catchAll = + if (hasDefault) None // no need for a catch-all when there's already a default + else Some(matchFail) + val expr = codegen.runOrElse(scrut, scrutSym, matcher, if (isFullyDefined(pt)) pt else NoType, catchAll) if (toHoist isEmpty) expr else Block(toHoist, expr) } @@ -966,7 +1024,7 @@ class Foo(x: Other) { x._1 } // no error in this order // TODO: do this during tree construction, but that will require tracking the current owner in treemakers // TODO: assign more fine-grained positions // fixes symbol nesting, assigns positions - private def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser { + protected def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser { currentOwner = origOwner override def traverse(t: Tree) { @@ -1019,7 +1077,7 @@ class Foo(x: Other) { x._1 } // no error in this order // codegen relevant to the structure of the translation (how extractors are combined) trait AbsCodegen { - def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): Tree + def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, catchAll: Option[Tree => Tree]): Tree def one(res: Tree, bodyPt: Type, matchPt: Type): Tree def zero: Tree def flatMap(prev: Tree, b: Symbol, next: Tree): Tree @@ -1098,10 +1156,10 @@ class Foo(x: Other) { x._1 } // no error in this order protected def matchMonadSym = oneSig.finalResultType.typeSymbol import CODE._ - def __match(n: Name): SelectStart = matchStrategy DOT n + def _match(n: Name): SelectStart = matchStrategy DOT n private lazy val oneSig: Type = - typer.typed(__match(vpmName.one), EXPRmode | POLYmode | TAPPmode | FUNmode, WildcardType).tpe // TODO: error message + typer.typed(_match(vpmName.one), EXPRmode | POLYmode | TAPPmode | FUNmode, WildcardType).tpe // TODO: error message } trait PureCodegen extends CodegenCore with PureMatchMonadInterface { @@ -1110,14 +1168,15 @@ class Foo(x: Other) { x._1 } // no error in this order object pureCodegen extends CommonCodegen { import CODE._ //// methods in MatchingStrategy (the monad companion) -- used directly in translation // __match.runOrElse(`scrut`)(`scrutSym` => `matcher`) - def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): Tree - = __match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, matcher)) + // TODO: consider catchAll, or virtualized matching will break in exception handlers + def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, catchAll: Option[Tree => Tree]): Tree + = _match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, matcher)) // __match.one(`res`) - def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = (__match(vpmName.one)) (res) + def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = (_match(vpmName.one)) (res) // __match.zero - def zero: Tree = __match(vpmName.zero) + def zero: Tree = _match(vpmName.zero) // __match.guard(`c`, `then`) - def guard(c: Tree, then: Tree, tp: Type): Tree = __match(vpmName.guard) APPLY (c, then) + def guard(c: Tree, then: Tree, tp: Type): Tree = _match(vpmName.guard) APPLY (c, then) //// methods in the monad instance -- used directly in translation // `prev`.flatMap(`b` => `next`) @@ -1437,94 +1496,145 @@ class Foo(x: Other) { x._1 } // no error in this order } } - //// SWITCHES + //// SWITCHES -- TODO: operate on Tests rather than TreeMakers trait SwitchEmission extends TreeMakers with OptimizedMatchMonadInterface { self: CodegenCore => - object SwitchablePattern { def unapply(pat: Tree) = pat match { - case Literal(Constant((_: Byte ) | (_: Short) | (_: Int ) | (_: Char ))) => true // TODO: Java 7 allows strings in switches - case _ => false - }} - - // def isSwitchable(cases: List[(List[TreeMaker], Tree)]): Boolean = { - // def isSwitchableTreeMaker(tm: TreeMaker) = tm match { - // case tm@EqualityTestTreeMaker(_, SwitchablePattern(), _) => true - // case SubstOnlyTreeMaker(_) => true - // case AlternativesTreeMaker(_, altss, _) => altss forall (_.forall(isSwitchableTreeMaker)) - // case _ => false - // } - // } + abstract class SwitchMaker { + abstract class SwitchableTreeMakerExtractor { def unapply(x: TreeMaker): Option[Tree] } + val SwitchableTreeMaker: SwitchableTreeMakerExtractor + + def alternativesSupported: Boolean - private val switchableTpes = Set(ByteClass.tpe, ShortClass.tpe, IntClass.tpe, CharClass.tpe) + def isDefault(x: CaseDef): Boolean + def defaultSym: Symbol + def defaultBody: Tree + def defaultCase(scrutSym: Symbol = defaultSym, body: Tree = defaultBody): CaseDef - override def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = { - def sequence[T](xs: List[Option[T]]): Option[List[T]] = + private def sequence[T](xs: List[Option[T]]): Option[List[T]] = if (xs exists (_.isEmpty)) None else Some(xs.flatten) - def isSwitchableTpe(tpe: Type): Boolean = - switchableTpes contains tpe - def switchableConstToInt(x: Tree): Tree = { - val Literal(const) = x - const.tag match { - case IntTag => x - case ByteTag | ShortTag | CharTag => Literal(Constant(const.intValue)) + // empty list ==> failure + def apply(cases: List[(Symbol, List[TreeMaker])], pt: Type): List[CaseDef] = { + val caseDefs = cases map { case (scrutSym, makers) => + makers match { + // default case + case (btm@BodyTreeMaker(body, _)) :: Nil => + Some(defaultCase(scrutSym, btm.substitution(body))) + // constant (or typetest for typeSwitch) + case SwitchableTreeMaker(pattern) :: (btm@BodyTreeMaker(body, _)) :: Nil => + Some(CaseDef(pattern, EmptyTree, btm.substitution(body))) + // alternatives + case AlternativesTreeMaker(_, altss, _) :: (btm@BodyTreeMaker(body, _)) :: Nil if alternativesSupported => + val casePatterns = altss map { + case SwitchableTreeMaker(pattern) :: Nil => + Some(pattern) + case _ => + None + } + + sequence(casePatterns) map { patterns => + val substedBody = btm.substitution(body) + CaseDef(Alternative(patterns), EmptyTree, substedBody) + } + case _ => //println("can't emit switch for "+ makers) + None //failure (can't translate pattern to a switch) + } } - } - val caseDefs = cases map { makers => - removeSubstOnly(makers) match { - // default case (don't move this to unfold, as it may only occur on the top level, not as an alternative -- well, except in degenerate matches) - case (btm@BodyTreeMaker(body, _)) :: Nil => - Some(CaseDef(Ident(nme.WILDCARD), EmptyTree, btm.substitution(body))) - // constant - case (EqualityTestTreeMaker(_, const@SwitchablePattern(), _)) :: (btm@BodyTreeMaker(body, _)) :: Nil => - Some(CaseDef(switchableConstToInt(const), EmptyTree, btm.substitution(body))) - // alternatives - case AlternativesTreeMaker(_, altss, _) :: (btm@BodyTreeMaker(body, _)) :: Nil => // assert(currLabel.isEmpty && nextLabel.isEmpty) - val caseConstants = altss map { - case EqualityTestTreeMaker(_, const@SwitchablePattern(), _) :: Nil => - Some(switchableConstToInt(const)) - case _ => - None + (for( + caseDefs <- sequence(caseDefs)) yield + if (caseDefs exists isDefault) caseDefs + else { + caseDefs :+ defaultCase() } + ) getOrElse Nil + } + } - sequence(caseConstants) map { contants => - val substedBody = btm.substitution(body) - CaseDef(Alternative(contants), EmptyTree, substedBody) - } - case _ => - None //failure (can't translate pattern to a switch) + class RegularSwitchMaker(scrutSym: Symbol) extends SwitchMaker { + val switchableTpe = Set(ByteClass.tpe, ShortClass.tpe, IntClass.tpe, CharClass.tpe) + val alternativesSupported = true + + object SwitchablePattern { def unapply(pat: Tree): Option[Tree] = pat match { + case Literal(const@Constant((_: Byte ) | (_: Short) | (_: Int ) | (_: Char ))) => + Some(Literal(Constant(const.intValue))) // TODO: Java 7 allows strings in switches + case _ => None + }} + + object SwitchableTreeMaker extends SwitchableTreeMakerExtractor { + def unapply(x: TreeMaker): Option[Tree] = x match { + case EqualityTestTreeMaker(_, SwitchablePattern(const), _) => Some(const) + case _ => None } } - if (!isSwitchableTpe(scrut.tpe)) - None // TODO: emit a cast of the scrutinee and a switch on the cast scrutinee if patterns allow switch but the type of the scrutinee doesn't - else { - sequence(caseDefs) map { caseDefs => - import CODE._ - val caseDefsWithDefault = { - def isDefault(x: CaseDef): Boolean = x match { - case CaseDef(Ident(nme.WILDCARD), EmptyTree, _) => true - case _ => false - } - val hasDefault = caseDefs exists isDefault - if (hasDefault) caseDefs else { - val default = atPos(scrut.pos) { DEFAULT ==> MATCHERROR(REF(scrutSym)) } - caseDefs :+ default - } - } - val matcher = BLOCK( - if (scrut.tpe != IntClass.tpe) { - scrutSym setInfo IntClass.tpe - VAL(scrutSym) === (scrut DOT nme.toInt) - } else { - VAL(scrutSym) === scrut - }, - Match(REF(scrutSym), caseDefsWithDefault) // match on scrutSym, not scrut to avoid duplicating scrut - ) - // matcher filter (tree => tree.tpe == null) foreach println - // treeBrowser browse matcher - matcher // set type to avoid recursion in typedMatch + def isDefault(x: CaseDef): Boolean = x match { + case CaseDef(Ident(nme.WILDCARD), EmptyTree, _) => true + case _ => false + } + + def defaultSym: Symbol = scrutSym + def defaultBody: Tree = { import CODE._; MATCHERROR(REF(scrutSym)) } + def defaultCase(scrutSym: Symbol = defaultSym, body: Tree = defaultBody): CaseDef = { import CODE._; atPos(body.pos) { + DEFAULT ==> body + }} + } + + override def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = { import CODE._ + val regularSwitchMaker = new RegularSwitchMaker(scrutSym) + // TODO: if patterns allow switch but the type of the scrutinee doesn't, cast (type-test) the scrutinee to the corresponding switchable type and switch on the result + if (regularSwitchMaker.switchableTpe(scrutSym.tpe)) { + val caseDefsWithDefault = regularSwitchMaker(cases map {c => (scrutSym, c)}, pt) + if (caseDefsWithDefault isEmpty) None + else { + // match on scrutSym -- converted to an int if necessary -- not on scrut directly (to avoid duplicating scrut) + val scrutToInt: Tree = + if(scrutSym.tpe =:= IntClass.tpe) REF(scrutSym) + else (REF(scrutSym) DOT (nme.toInt)) + Some(BLOCK( + VAL(scrutSym) === scrut, + Match(scrutToInt, caseDefsWithDefault) + )) + } + } else None + } + + // for the catch-cases in a try/catch + private object typeSwitchMaker extends SwitchMaker { + def switchableTpe(tp: Type) = true + val alternativesSupported = false // TODO: needs either back-end support of flattening of alternatives during typers + + // TODO: there are more treemaker-sequences that can be handled by type tests + // analyze the result of approximateTreeMaker rather than the TreeMaker itself + object SwitchableTreeMaker extends SwitchableTreeMakerExtractor { + def unapply(x: TreeMaker): Option[Tree] = x match { + case tm@TypeTestTreeMaker(_, _, _) => + Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(tm.nextBinderTp)) /* not used by back-end */)) // -- TODO: use this if binder does not occur in the body + case tm@TypeAndEqualityTestTreeMaker(_, patBinder, pt, _) if tm.isStraightTypeTest => + Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(tm.nextBinderTp)) /* not used by back-end */)) + case _ => + None } } + + def isDefault(x: CaseDef): Boolean = x match { + case CaseDef(Typed(Ident(nme.WILDCARD), tpt), EmptyTree, _) if (tpt.tpe =:= ThrowableClass.tpe) => true + case CaseDef(Bind(_, Typed(Ident(nme.WILDCARD), tpt)), EmptyTree, _) if (tpt.tpe =:= ThrowableClass.tpe) => true + case CaseDef(Ident(nme.WILDCARD), EmptyTree, _) => true + case _ => false + } + + lazy val defaultSym: Symbol = freshSym(NoPosition, ThrowableClass.tpe) + def defaultBody: Tree = Throw(CODE.REF(defaultSym)) + def defaultCase(scrutSym: Symbol = defaultSym, body: Tree = defaultBody): CaseDef = { import CODE._; atPos(body.pos) { + CASE (Bind(scrutSym, Typed(Ident(nme.WILDCARD), TypeTree(ThrowableClass.tpe)))) ==> body + }} + } + + // TODO: drop null checks + override def emitTypeSwitch(bindersAndCases: List[(Symbol, List[TreeMaker])], pt: Type): Option[List[CaseDef]] = { + val caseDefsWithDefault = typeSwitchMaker(bindersAndCases, pt) + if (caseDefsWithDefault isEmpty) None + else Some(caseDefsWithDefault) } } @@ -1551,33 +1661,31 @@ class Foo(x: Other) { x._1 } // no error in this order /** Inline runOrElse and get rid of Option allocations * - * runOrElse(scrut: scrutTp)(matcher): resTp = matcher(scrut) getOrElse (throw new MatchError(x)) + * runOrElse(scrut: scrutTp)(matcher): resTp = matcher(scrut) getOrElse ${catchAll(`scrut`)} * 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 - def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean) = { + def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, catchAll: Option[Tree => Tree]) = { 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(scrutSym) === scrut, // reuse the symbol of the function's argument to avoid creating a fresh one and substituting it for scrutSym in `matcher` -- the owner structure is repaired by fixerUpper + VAL(scrutSym) === scrut, VAL(matchRes) === mkZero(matchRes.info), // must cast to deal with GADT typing, hence the private mkZero above VAL(keepGoing) === TRUE, matcher, - if(hasDefault) REF(matchRes) - else (IF (REF(keepGoing)) THEN MATCHERROR(REF(scrutSym)) ELSE REF(matchRes)) + catchAll map { catchAllGen => (IF (REF(keepGoing)) THEN catchAllGen(REF(scrutSym)) ELSE REF(matchRes)) } getOrElse REF(matchRes) ) } // only used to wrap the RHS of a body def one(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, + REF(keepGoing) === FALSE, // comes before assignment to matchRes, so the latter is in tail positions (can ignore the trailing zero -- will disappear when we flatten blocks, which is TODO) + if (dontStore(matchPt)) res else (REF(matchRes) === res), // runOrElse hasn't been called yet, so matchRes.isMutable is irrelevant, also, tp may be a subtype of resTp used in runOrElse... 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 ) } diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index ef69e1525e..23fc30b9fb 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -1987,7 +1987,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { treeCopy.CaseDef(cdef, pat1, guard1, body1) setType body1.tpe } - def typedCases(tree: Tree, cases: List[CaseDef], pattp: Type, pt: Type): List[CaseDef] = + def typedCases(cases: List[CaseDef], pattp: Type, pt: Type): List[CaseDef] = cases mapConserve { cdef => newTyper(context.makeNewScope(cdef, context.owner)).typedCase(cdef, pattp, pt) } @@ -3318,7 +3318,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { typed1(atPos(tree.pos) { Function(params, body) }, mode, pt) } else { val selector1 = checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType)) - var cases1 = typedCases(tree, cases, packCaptured(selector1.tpe.widen), pt) + var cases1 = typedCases(cases, packCaptured(selector1.tpe.widen), pt) if (isPastTyper || !opt.virtPatmat) { val (owntype, needAdapt) = ptOrLub(cases1 map (_.tpe)) @@ -3334,7 +3334,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { (MatchTranslator(this)).translateMatch(selector1, cases1, owntype) match { case Block(vd :: Nil, tree@Match(selector, cases)) => val selector1 = checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType)) - var cases1 = typedCases(tree, cases, packCaptured(selector1.tpe.widen), pt) + var cases1 = typedCases(cases, packCaptured(selector1.tpe.widen), pt) val (owntype, needAdapt) = ptOrLub(cases1 map (_.tpe)) if (needAdapt) cases1 = cases1 map (adaptCase(_, owntype)) @@ -4242,7 +4242,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { case Try(block, catches, finalizer) => var block1 = typed(block, pt) - var catches1 = typedCases(tree, catches, ThrowableClass.tpe, pt) + var catches1 = typedCases(catches, ThrowableClass.tpe, pt) val finalizer1 = if (finalizer.isEmpty) finalizer else typed(finalizer, UnitClass.tpe) val (owntype, needAdapt) = ptOrLub(block1.tpe :: (catches1 map (_.tpe))) @@ -4250,6 +4250,11 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { block1 = adapt(block1, mode, owntype) catches1 = catches1 map (adaptCase(_, owntype)) } + + if(!isPastTyper && opt.virtPatmat) { + catches1 = (MatchTranslator(this)).translateTry(catches1, owntype, tree.pos) + } + treeCopy.Try(tree, block1, catches1, finalizer1) setType owntype case Throw(expr) => diff --git a/src/continuations/plugin/scala/tools/selectivecps/SelectiveCPSTransform.scala b/src/continuations/plugin/scala/tools/selectivecps/SelectiveCPSTransform.scala index b2a1546b4e..a90dc36639 100644 --- a/src/continuations/plugin/scala/tools/selectivecps/SelectiveCPSTransform.scala +++ b/src/continuations/plugin/scala/tools/selectivecps/SelectiveCPSTransform.scala @@ -203,7 +203,7 @@ abstract class SelectiveCPSTransform extends PluginComponent with rhs.changeOwner(currentOwner -> fun.symbol) val exSym = currentOwner.newValueParameter(cpsNames.ex, pos).setInfo(ThrowableClass.tpe) - val catch2 = { localTyper.typedCases(tree, List( + val catch2 = { localTyper.typedCases(List( CaseDef(Bind(exSym, Typed(Ident("_"), TypeTree(ThrowableClass.tpe))), Apply(Select(Ident(funSym), nme.isDefinedAt), List(Ident(exSym))), Apply(Ident(funSym), List(Ident(exSym)))) diff --git a/src/library/scala/sys/process/BasicIO.scala b/src/library/scala/sys/process/BasicIO.scala index 5b7244e98e..edc60a1bb5 100644 --- a/src/library/scala/sys/process/BasicIO.scala +++ b/src/library/scala/sys/process/BasicIO.scala @@ -227,9 +227,10 @@ object BasicIO { out.write(buffer, 0, byteCount) // flush() will throw an exception once the process has terminated val available = try { out.flush(); true } catch { case _: IOException => false } - if (available) loop() else in.close() - } else in.close() + if (available) loop() + } } loop() + in.close() } } diff --git a/test/files/run/virtpatmat_partial.check b/test/files/run/virtpatmat_partial.check index 093020ce05..1555eca82b 100644 --- a/test/files/run/virtpatmat_partial.check +++ b/test/files/run/virtpatmat_partial.check @@ -1,2 +1,4 @@ Map(a -> Some(1), b -> None) -Map(a -> 1)
\ No newline at end of file +79 +undefined +Map(a -> 1) diff --git a/test/files/run/virtpatmat_partial.scala b/test/files/run/virtpatmat_partial.scala index c408b31983..6597f2f5ae 100644 --- a/test/files/run/virtpatmat_partial.scala +++ b/test/files/run/virtpatmat_partial.scala @@ -4,6 +4,29 @@ object Test extends App { val res = a collect {case (p, Some(a)) => (p, a)} + final val GT = 79 + final val GTGT = 93 + final val GTGTGT = 94 + final val GTEQ = 81 + final val GTGTEQ = 113 + final val GTGTGTEQ = 114 + final val ASSIGN = 75 + + def acceptClosingAngle(in: Int) { + val closers: PartialFunction[Int, Int] = { + case GTGTGTEQ => GTGTEQ + case GTGTGT => GTGT + case GTGTEQ => GTEQ + case GTGT => GT + case GTEQ => ASSIGN + } + if (closers isDefinedAt in) println(closers(in)) + else println("undefined") + } + + acceptClosingAngle(GTGT) + acceptClosingAngle(ASSIGN) + // should uncurry to: // val res: Map[String,Int] = a.collect[(String, Int), Map[String,Int]]( // new PartialFunction[(String, Option[Int]),(String, Int)] { diff --git a/test/files/run/virtpatmat_switch.scala b/test/files/run/virtpatmat_switch.scala index 2e2c31e8e5..1329c19d0f 100644 --- a/test/files/run/virtpatmat_switch.scala +++ b/test/files/run/virtpatmat_switch.scala @@ -14,9 +14,15 @@ object Test extends App { case 'b' => "got b" case _ => "got some letter" } + + def byteSwitch(x: Byte) = x match { + case 'a' => "got a" + case 'b' => "got b" + case _ => "got some letter" + } println(charSwitch('a')) - println(charSwitch('b')) + println(byteSwitch('b')) println(charSwitch('z')) def implicitDefault(x: Int) = x match { diff --git a/test/files/run/virtpatmat_try.check b/test/files/run/virtpatmat_try.check new file mode 100644 index 0000000000..80ebbf494a --- /dev/null +++ b/test/files/run/virtpatmat_try.check @@ -0,0 +1,2 @@ +meh +B diff --git a/test/files/run/virtpatmat_try.flags b/test/files/run/virtpatmat_try.flags new file mode 100644 index 0000000000..9769db9257 --- /dev/null +++ b/test/files/run/virtpatmat_try.flags @@ -0,0 +1 @@ + -Yvirtpatmat -Xexperimental diff --git a/test/files/run/virtpatmat_try.scala b/test/files/run/virtpatmat_try.scala new file mode 100644 index 0000000000..46e67cb72e --- /dev/null +++ b/test/files/run/virtpatmat_try.scala @@ -0,0 +1,47 @@ +object Test extends App { + case class A(val x: String) extends Throwable + class B extends Exception { override def toString = "B" } + def bla = 0 + + try { + throw new A("meh") + } catch { // this should emit a "catch-switch" + case y: A => println(y.x) + case (_ : A | _ : B) => println("B") + case _ => println("other") + } + + try { + throw new B() + } catch { // case classes and alternative flattening aren't supported yet, but could be in principle + // case A(x) => println(x) + case y: A => println(y.x) + case x@((_ : A) | (_ : B)) => println(x) + case _ => println("other") + } + + def simpleTry { + try { + bla + } catch { + case x: Exception if x.getMessage == "test" => println("first case " + x) + case x: Exception => println("second case " + x) + } + } + + def typedWildcardTry { + try { bla } catch { case _: ClassCastException => bla } + } + + def wildcardTry { + try { bla } catch { case _ => bla } + } + + def tryPlusFinally { + try { bla } finally { println("finally") } + } + + def catchAndPassToLambda { + try { bla } catch { case ex: Exception => val f = () => ex } + } +}
\ No newline at end of file diff --git a/test/files/specialized/SI-5005.scala b/test/files/specialized/SI-5005.scala index cc9d327b08..3d1ada49e2 100644 --- a/test/files/specialized/SI-5005.scala +++ b/test/files/specialized/SI-5005.scala @@ -17,7 +17,11 @@ object Test extends DirectTest { override def show(): Unit = { // redirect err to out, for inliner log - System.setErr(new PrintStream(System.out)); + val prevErr = System.err + System.setErr(System.out) compile() + System.setErr(prevErr) } + + override def isDebug = false // so we don't get the newSettings warning } |