diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala')
| -rw-r--r-- | src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala | 725 |
1 files changed, 0 insertions, 725 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala deleted file mode 100644 index 64c9901a3e..0000000000 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ /dev/null @@ -1,725 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Martin Odersky - */ - -package scala -package tools.nsc -package backend.icode.analysis - -import scala.collection.{mutable, immutable} -import java.util.concurrent.TimeUnit - -/** A data-flow analysis on types, that works on `ICode`. - * - * @author Iulian Dragos - */ -abstract class TypeFlowAnalysis { - val global: Global - import global._ - import definitions.{ ObjectClass, NothingClass, AnyRefClass, StringClass, ThrowableClass } - - /** The lattice of ICode types. - */ - object typeLattice extends SemiLattice { - type Elem = icodes.TypeKind - - val top = icodes.REFERENCE(ObjectClass) - val bottom = icodes.REFERENCE(NothingClass) - - def lub2(exceptional: Boolean)(a: Elem, b: Elem) = - if (a eq bottom) b - else if (b eq bottom) a - else icodes.lub(a, b) - } - - /** The lattice of type stacks. It is a straight forward extension of - * the type lattice (lub is pairwise lub of the list elements). - */ - object typeStackLattice extends SemiLattice { - import icodes._ - type Elem = TypeStack - - val top = new TypeStack - val bottom = new TypeStack - val exceptionHandlerStack = new TypeStack(List(REFERENCE(AnyRefClass))) - - def lub2(exceptional: Boolean)(s1: TypeStack, s2: TypeStack) = { - if (s1 eq bottom) s2 - else if (s2 eq bottom) s1 - else if ((s1 eq exceptionHandlerStack) || (s2 eq exceptionHandlerStack)) sys.error("merging with exhan stack") - else { -// if (s1.length != s2.length) -// throw new CheckerException("Incompatible stacks: " + s1 + " and " + s2); - new TypeStack((s1.types, s2.types).zipped map icodes.lub) - } - } - } - - /** A map which returns the bottom type for unfound elements */ - class VarBinding extends mutable.HashMap[icodes.Local, icodes.TypeKind] { - override def default(l: icodes.Local) = typeLattice.bottom - - def this(o: VarBinding) = { - this() - this ++= o - } - } - - /** The type flow lattice contains a binding from local variable - * names to types and a type stack. - */ - object typeFlowLattice extends SemiLattice { - type Elem = IState[VarBinding, icodes.TypeStack] - - val top = new Elem(new VarBinding, typeStackLattice.top) - val bottom = new Elem(new VarBinding, typeStackLattice.bottom) - - def lub2(exceptional: Boolean)(a: Elem, b: Elem) = { - val IState(env1, _) = a - val IState(env2, _) = b - - val resultingLocals = new VarBinding - env1 foreach { case (k, v) => - resultingLocals += ((k, typeLattice.lub2(exceptional)(v, env2(k)))) - } - env2 collect { case (k, v) if resultingLocals(k) eq typeLattice.bottom => - resultingLocals += ((k, typeLattice.lub2(exceptional)(v, env1(k)))) - } - val stack = - if (exceptional) typeStackLattice.exceptionHandlerStack - else typeStackLattice.lub2(exceptional)(a.stack, b.stack) - - IState(resultingLocals, stack) - } - } - - val timer = new Timer - - class MethodTFA extends DataFlowAnalysis[typeFlowLattice.type] { - import icodes._ - import icodes.opcodes._ - - type P = BasicBlock - val lattice = typeFlowLattice - - val STRING = icodes.REFERENCE(StringClass) - var method: IMethod = _ - - /** Initialize the in/out maps for the analysis of the given method. */ - def init(m: icodes.IMethod) { - this.method = m - //typeFlowLattice.lubs = 0 - init { - worklist += m.startBlock - worklist ++= (m.exh map (_.startBlock)) - m foreachBlock { b => - in(b) = typeFlowLattice.bottom - out(b) = typeFlowLattice.bottom - } - - // start block has var bindings for each of its parameters - val entryBindings = new VarBinding ++= (m.params map (p => ((p, p.kind)))) - in(m.startBlock) = lattice.IState(entryBindings, typeStackLattice.bottom) - - m.exh foreach { e => - in(e.startBlock) = lattice.IState(in(e.startBlock).vars, typeStackLattice.exceptionHandlerStack) - } - } - } - - def this(m: icodes.IMethod) { - this() - init(m) - } - - def run() = { - timer.start() - // icodes.lubs0 = 0 - forwardAnalysis(blockTransfer) - timer.stop - if (settings.debug) { - linearizer.linearize(method).foreach(b => if (b != method.startBlock) - 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") - } - - def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { - 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) { - // Console.println("[before] Stack: " + stack); - // Console.println(i); - } - i match { - - case THIS(clasz) => stack push toTypeKind(clasz.tpe) - case CONSTANT(const) => stack push toTypeKind(const.tpe) - - case LOAD_ARRAY_ITEM(kind) => - stack.pop2 match { - case (idxKind, ARRAY(elem)) => - assert(idxKind == INT || idxKind == CHAR || idxKind == SHORT || idxKind == BYTE) - stack.push(elem) - case (_, _) => - 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 cm @ CALL_METHOD(_, _) => - stack pop cm.consumed - cm.producedTypes foreach (stack push _) - - 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 => stack.pop - case _: JUMP => () - case _: CJUMP => stack.pop2 - case _: CZJUMP => 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() | MONITOR_EXIT() => stack.pop - - case SCOPE_ENTER(_) | SCOPE_EXIT(_) => () - - case LOAD_EXCEPTION(clasz) => - stack.pop(stack.length) - stack.push(toTypeKind(clasz.tpe)) - - case _ => - dumpClassesAndAbort("Unknown instruction: " + i) - } - out - } // interpret - - abstract class InferredType { - /** Return the type kind pointed by this inferred type. */ - def getKind(in: lattice.Elem): icodes.TypeKind = this match { - case Const(k) => - k - case TypeOfVar(l: icodes.Local) => - if (in.vars.isDefinedAt(l)) in.vars(l) else l.kind - case TypeOfStackPos(n: Int) => - assert(in.stack.length >= n) - in.stack(n) - } - } - /** A type that does not depend on input to the transfer function. */ - case class Const(t: icodes.TypeKind) extends InferredType - /** The type of a given local variable. */ - case class TypeOfVar(l: icodes.Local) extends InferredType - /** The type found at a stack position. */ - case class TypeOfStackPos(n: Int) extends InferredType - - abstract class Gen - case class Bind(l: icodes.Local, t: InferredType) extends Gen - case class Push(t: InferredType) extends Gen - - /** A flow transfer function of a basic block. */ - class TransferFunction(consumed: Int, gens: List[Gen]) extends (lattice.Elem => lattice.Elem) { - def apply(in: lattice.Elem): lattice.Elem = { - val out = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack)) - val stack = out.stack - - out.stack.pop(consumed) - for (g <- gens) g match { - case Bind(l, t) => - out.vars += (l -> t.getKind(in)) - case Push(t) => - stack.push(t.getKind(in)) - } - out - } - } - } - - 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 visited 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 overriding 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._ - - 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) - 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) { - 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 decision 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.isEffectivelyFinalOrNotOverridden || receiver.isEffectivelyFinalOrNotOverridden ) && - !blackballed(concreteMethod) - } - if(isCandidate) { - remainingCALLs(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] - - val warnIfInlineFails = mutable.Set.empty[opcodes.CALL_METHOD] // cache for a given IMethod (ie cleared on Inliner.analyzeMethod). - - /* 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`) - final def blackballed(msym: Symbol): Boolean = { knownUnsafe(msym) || knownNever(msym) } - - val relevantBBs = mutable.Set.empty[BasicBlock] - - /* - * Rationale to prevent some methods from ever being inlined: - * - * (1) inlining getters and setters results in exposing a private field, - * which may itself prevent inlining of the caller (at best) or - * lead to situations like SI-5442 ("IllegalAccessError when mixing optimized and unoptimized bytecode") - * - * (2) only invocations having a receiver object are considered (ie no static-methods are ever inlined). - * This is taken care of by checking `isDynamic` (ie virtual method dispatch) and `Static(true)` (ie calls to private members) - */ - private def isPreCandidate(cm: opcodes.CALL_METHOD): Boolean = { - val msym = cm.method - val style = cm.style - - !blackballed(msym) && - !msym.isConstructor && - (!msym.isAccessor || inliner.isClosureClass(msym.owner)) && - (style.isDynamic || (style.hasInstance && style.isStatic)) - } - - 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() - warnIfInlineFails.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() - // usually but not always true (counterexample in SI-6015) `(relevantBBs.isEmpty || relevantBBs.contains(m.startBlock))` - } - - 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.isEffectivelyFinalOrNotOverridden && cm.method.owner.isEffectivelyFinalOrNotOverridden - } - - private def putOnRadar(blocks: Traversable[BasicBlock]) { - for(bb <- blocks) { - val calls = bb.toList collect { case cm : opcodes.CALL_METHOD => cm } - for(c <- calls; if(inliner.hasInline(c.method))) { - warnIfInlineFails += c - } - val preCands = calls filter isPreCandidate - isOnWatchlist ++= preCands - } - relevantBBs ++= blocks - } - - /* 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 - } - - /* 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; 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 appeared - 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: scala.collection.Set[BasicBlock], staleIn: scala.collection.Set[BasicBlock]) { - if (this.method == null || this.method.symbol != m.symbol) { - init(m) - return - } else if(staleOut.isEmpty && inlined.isEmpty && staleIn.isEmpty) { - // this promotes invoking reinit if in doubt, no performance degradation will ensue! - return - } - - 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 } - } - - private def blankOut(blocks: scala.collection.Set[BasicBlock]) { - blocks foreach { b => - 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 existing = in(p) - // TODO move the following assertion to typeFlowLattice.lub2 for wider applicability (ie MethodTFA in addition to MTFAGrowable). - assert(existing == lattice.bottom || - p.exceptionHandlerStart || - (output.stack.length == existing.stack.length), - "Trying to merge non-bottom type-stacks with different stack heights. For a possible cause see SI-6157.") - val updated = lattice.lub(List(output, existing), p.exceptionHandlerStart) - if(updated != in(p)) { - in(p) = updated - enqueue(p) - } - } - } - } - } - } - } - - } - - class Timer { - var millis = 0L - - private var lastStart = 0L - - def start() { - lastStart = System.nanoTime() - } - - /** Stop the timer and return the number of milliseconds since the last - * call to start. The 'millis' field is increased by the elapsed time. - */ - def stop: Long = { - val elapsed = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - lastStart) - millis += elapsed - elapsed - } - } -} |