Refactor coverage analysis package (#744)

* Encapsulate insn/branch status tracking in Instruction
* Move Instruction to the analysis package
* Encapsulate Instruction building in new class InstructionsBuilder
* Separate coverage calculation from filtering

7 files changed, 639 insertions, 443 deletions

diff --git a/org.jacoco.core/src/org/jacoco/core/internal/analysis/ClassAnalyzer.java b/org.jacoco.core/src/org/jacoco/core/internal/analysis/ClassAnalyzer.java
index e40b66dc..02bc380a 100644
--- a/org.jacoco.core/src/org/jacoco/core/internal/analysis/ClassAnalyzer.java
+++ b/org.jacoco.core/src/org/jacoco/core/internal/analysis/ClassAnalyzer.java
@@ -14,14 +14,16 @@ package org.jacoco.core.internal.analysis;
 import java.util.HashSet;
 import java.util.Set;
 
-import org.jacoco.core.analysis.IMethodCoverage;
 import org.jacoco.core.internal.analysis.filter.Filters;
+import org.jacoco.core.internal.analysis.filter.IFilter;
 import org.jacoco.core.internal.analysis.filter.IFilterContext;
 import org.jacoco.core.internal.flow.ClassProbesVisitor;
 import org.jacoco.core.internal.flow.MethodProbesVisitor;
 import org.jacoco.core.internal.instr.InstrSupport;
 import org.objectweb.asm.AnnotationVisitor;
 import org.objectweb.asm.FieldVisitor;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.tree.MethodNode;
 
 /**
  * Analyzes the structure of a class.
@@ -29,6 +31,8 @@ import org.objectweb.asm.FieldVisitor;
 public class ClassAnalyzer extends ClassProbesVisitor
 		implements IFilterContext {
 
+	private final IFilter filter = Filters.ALL;
+
 	private final ClassCoverageImpl coverage;
 	private final boolean[] probes;
 	private final StringPool stringPool;
@@ -80,21 +84,38 @@ public class ClassAnalyzer extends ClassProbesVisitor
 
 		InstrSupport.assertNotInstrumented(name, coverage.getName());
 
-		return new MethodAnalyzer(stringPool.get(name), stringPool.get(desc),
-				stringPool.get(signature), probes, Filters.ALL, this) {
+		final InstructionsBuilder builder = new InstructionsBuilder(probes);
+
+		return new MethodAnalyzer(builder) {
+
 			@Override
-			public void visitEnd() {
-				super.visitEnd();
-				final IMethodCoverage methodCoverage = getCoverage();
-				if (methodCoverage.getInstructionCounter()
-						.getTotalCount() > 0) {
-					// Only consider methods that actually contain code
-					coverage.addMethod(methodCoverage);
-				}
+			public void accept(final MethodNode methodNode,
+					final MethodVisitor methodVisitor) {
+				super.accept(methodNode, methodVisitor);
+				addMethodCoverage(stringPool.get(name), stringPool.get(desc),
+						stringPool.get(signature), builder, methodNode);
 			}
 		};
 	}
 
+	private void addMethodCoverage(final String name, final String desc,
+			final String signature, final InstructionsBuilder icc,
+			final MethodNode methodNode) {
+		final MethodCoverageCalculator mcc = new MethodCoverageCalculator(
+				icc.getInstructions());
+		filter.filter(methodNode, this, mcc);
+
+		final MethodCoverageImpl mc = new MethodCoverageImpl(name, desc,
+				signature);
+		mcc.calculate(mc);
+
+		if (mc.getInstructionCounter().getTotalCount() > 0) {
+			// Only consider methods that actually contain code
+			coverage.addMethod(mc);
+		}
+
+	}
+
 	@Override
 	public FieldVisitor visitField(final int access, final String name,
 			final String desc, final String signature, final Object value) {
diff --git a/org.jacoco.core/src/org/jacoco/core/internal/analysis/Instruction.java b/org.jacoco.core/src/org/jacoco/core/internal/analysis/Instruction.java
new file mode 100644
index 00000000..ea6eb829
--- /dev/null
+++ b/org.jacoco.core/src/org/jacoco/core/internal/analysis/Instruction.java
@@ -0,0 +1,207 @@
+/*******************************************************************************
+ * Copyright (c) 2009, 2018 Mountainminds GmbH & Co. KG and Contributors
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *    Marc R. Hoffmann - initial API and implementation
+ *    
+ *******************************************************************************/
+package org.jacoco.core.internal.analysis;
+
+import java.util.BitSet;
+import java.util.Collection;
+
+import org.jacoco.core.analysis.ICounter;
+
+/**
+ * Execution status of a single bytecode instruction internally used for
+ * coverage analysis. The execution status is recorded separately for each
+ * outgoing branch. Each instruction has at least one branch, for example in
+ * case of a simple sequence of instructions (by convention branch 0). Instances
+ * of this class are used in two steps:
+ * 
+ * <h3>Step 1: Building the CFG</h3>
+ * 
+ * For each bytecode instruction of a method a {@link Instruction} instance is
+ * created. In correspondence with the CFG these instances are linked with each
+ * other with the <code>addBranch()</code> methods. The executions status is
+ * either directly derived from a probe which has been inserted in the execution
+ * flow ({@link #addBranch(boolean, int)}) or indirectly propagated along the
+ * CFG edges ({@link #addBranch(Instruction, int)}).
+ * 
+ * <h3>Step 2: Querying the Coverage Status</h3>
+ * 
+ * After all instructions have been created and linked each instruction knows
+ * its execution status and can be queried with:
+ * 
+ * <ul>
+ * <li>{@link #getLine()}</li>
+ * <li>{@link #getInstructionCounter()}</li>
+ * <li>{@link #getBranchCounter()}</li>
+ * </ul>
+ * 
+ * For the purpose of filtering instructions can be combined to new
+ * instructions. Note that these methods create new {@link Instruction}
+ * instances and do not modify the existing ones.
+ * 
+ * <ul>
+ * <li>{@link #merge(Instruction)}</li>
+ * <li>{@link #replaceBranches(Collection)}</li>
+ * </ul>
+ */
+public class Instruction {
+
+	private final int line;
+
+	private int branches;
+
+	private final BitSet coveredBranches;
+
+	private Instruction predecessor;
+
+	private int predecessorBranch;
+
+	/**
+	 * New instruction at the given line.
+	 * 
+	 * @param line
+	 *            source line this instruction belongs to
+	 */
+	public Instruction(final int line) {
+		this.line = line;
+		this.branches = 0;
+		this.coveredBranches = new BitSet();
+	}
+
+	/**
+	 * Adds a branch to this instruction which execution status is indirectly
+	 * derived from the execution status of the target instruction. In case the
+	 * branch is covered the status is propagated also to the predecessors of
+	 * this instruction.
+	 * 
+	 * Note: This method is not idempotent and must be called exactly once for
+	 * every branch.
+	 * 
+	 * @param target
+	 *            target instruction of this branch
+	 * @param branch
+	 *            branch identifier unique for this instruction
+	 */
+	public void addBranch(final Instruction target, final int branch) {
+		branches++;
+		target.predecessor = this;
+		target.predecessorBranch = branch;
+		if (!target.coveredBranches.isEmpty()) {
+			propagateExecutedBranch(this, branch);
+		}
+	}
+
+	/**
+	 * Adds a branch to this instruction which execution status is directly
+	 * derived from a probe. In case the branch is covered the status is
+	 * propagated also to the predecessors of this instruction.
+	 * 
+	 * Note: This method is not idempotent and must be called exactly once for
+	 * every branch.
+	 * 
+	 * @param executed
+	 *            whether the corresponding probe has been executed
+	 * @param branch
+	 *            branch identifier unique for this instruction
+	 */
+	public void addBranch(final boolean executed, final int branch) {
+		branches++;
+		if (executed) {
+			propagateExecutedBranch(this, branch);
+		}
+	}
+
+	private static void propagateExecutedBranch(Instruction insn, int branch) {
+		// No recursion here, as there can be very long chains of instructions
+		while (insn != null) {
+			if (!insn.coveredBranches.isEmpty()) {
+				insn.coveredBranches.set(branch);
+				break;
+			}
+			insn.coveredBranches.set(branch);
+			branch = insn.predecessorBranch;
+			insn = insn.predecessor;
+		}
+	}
+
+	/**
+	 * Returns the source line this instruction belongs to.
+	 * 
+	 * @return corresponding source line
+	 */
+	public int getLine() {
+		return line;
+	}
+
+	/**
+	 * Merges information about covered branches of this instruction with
+	 * another instruction.
+	 * 
+	 * @param other
+	 *            instruction to merge with
+	 * @return new instance with merged branches
+	 */
+	public Instruction merge(final Instruction other) {
+		final Instruction result = new Instruction(this.line);
+		result.branches = this.branches;
+		result.coveredBranches.or(this.coveredBranches);
+		result.coveredBranches.or(other.coveredBranches);
+		return result;
+	}
+
+	/**
+	 * Creates a copy of this instruction where all outgoing branches are
+	 * replaced with the given instructions. The coverage status of the new
+	 * instruction is derived from the status of the given instructions.
+	 * 
+	 * @param newBranches
+	 *            new branches to consider
+	 * @return new instance with replaced branches
+	 */
+	public Instruction replaceBranches(
+			final Collection<Instruction> newBranches) {
+		final Instruction result = new Instruction(this.line);
+		result.branches = newBranches.size();
+		int idx = 0;
+		for (final Instruction b : newBranches) {
+			if (!b.coveredBranches.isEmpty()) {
+				result.coveredBranches.set(idx++);
+			}
+		}
+		return result;
+	}
+
+	/**
+	 * Returns the instruction coverage counter of this instruction. It is
+	 * always 1 instruction which is covered or not.
+	 * 
+	 * @return the instruction coverage counter
+	 */
+	public ICounter getInstructionCounter() {
+		return coveredBranches.isEmpty() ? CounterImpl.COUNTER_1_0
+				: CounterImpl.COUNTER_0_1;
+	}
+
+	/**
+	 * Returns the branch coverage counter of this instruction. Only
+	 * instructions with at least 2 outgoing edges report branches.
+	 * 
+	 * @return the branch coverage counter
+	 */
+	public ICounter getBranchCounter() {
+		if (branches < 2) {
+			return CounterImpl.COUNTER_0_0;
+		}
+		final int covered = coveredBranches.cardinality();
+		return CounterImpl.getInstance(branches - covered, covered);
+	}
+
+}
diff --git a/org.jacoco.core/src/org/jacoco/core/internal/analysis/InstructionsBuilder.java b/org.jacoco.core/src/org/jacoco/core/internal/analysis/InstructionsBuilder.java
new file mode 100644
index 00000000..41c602ea
--- /dev/null
+++ b/org.jacoco.core/src/org/jacoco/core/internal/analysis/InstructionsBuilder.java
@@ -0,0 +1,186 @@
+/*******************************************************************************
+ * Copyright (c) 2009, 2018 Mountainminds GmbH & Co. KG and Contributors
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *    Marc R. Hoffmann - initial API and implementation
+ *    
+ *******************************************************************************/
+package org.jacoco.core.internal.analysis;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.jacoco.core.analysis.ISourceNode;
+import org.jacoco.core.internal.flow.LabelInfo;
+import org.objectweb.asm.Label;
+import org.objectweb.asm.tree.AbstractInsnNode;
+
+/**
+ * Stateful builder for the {@link Instruction}s of a method. All instructions
+ * of a method must be added in their original sequence along with additional
+ * information like line numbers. Afterwards the instructions can be obtained
+ * with the <code>getInstructions()</code> method.
+ */
+class InstructionsBuilder {
+
+	/** Probe array of the class the analyzed method belongs to. */
+	private final boolean[] probes;
+
+	/** The line which belong to subsequently added instructions. */
+	private int currentLine;
+
+	/** The last instruction which has been added. */
+	private Instruction currentInsn;
+
+	/**
+	 * All instructions of a method mapped from the ASM node to the
+	 * corresponding {@link Instruction} instance.
+	 */
+	private final Map<AbstractInsnNode, Instruction> instructions;
+
+	/**
+	 * The labels which mark the subsequent instructions.
+	 * 
+	 * Due to ASM issue #315745 there can be more than one label per instruction
+	 */
+	private final List<Label> currentLabel;
+
+	/**
+	 * List of all jumps within the control flow. We need to store jumps
+	 * temporarily as the target {@link Instruction} may not been known yet.
+	 */
+	private final List<Jump> jumps;
+
+	/**
+	 * Creates a new builder instance which can be used to analyze a single
+	 * method.
+	 * 
+	 * @param probes
+	 *            probe array of the corresponding class used to determine the
+	 *            coverage status of every instruction.
+	 */
+	InstructionsBuilder(final boolean[] probes) {
+		this.probes = probes;
+		this.currentLine = ISourceNode.UNKNOWN_LINE;
+		this.currentInsn = null;
+		this.instructions = new HashMap<AbstractInsnNode, Instruction>();
+		this.currentLabel = new ArrayList<Label>(2);
+		this.jumps = new ArrayList<Jump>();
+	}
+
+	/**
+	 * Sets the current source line. All subsequently added instructions will be
+	 * assigned to this line. If no line is set (e.g. for classes compiled
+	 * without debug information) {@link ISourceNode#UNKNOWN_LINE} is assigned
+	 * to the instructions.
+	 */
+	void setCurrentLine(final int line) {
+		currentLine = line;
+	}
+
+	/**
+	 * Adds a label which applies to the subsequently added instruction. Due to
+	 * ASM internals multiple {@link Label}s can be added to an instruction.
+	 */
+	void addLabel(final Label label) {
+		currentLabel.add(label);
+		if (!LabelInfo.isSuccessor(label)) {
+			noSuccessor();
+		}
+	}
+
+	/**
+	 * Adds a new instruction. Instructions are by default linked with the
+	 * previous instruction unless specified otherwise.
+	 */
+	void addInstruction(final AbstractInsnNode node) {
+		final Instruction insn = new Instruction(currentLine);
+		final int labelCount = currentLabel.size();
+		if (labelCount > 0) {
+			for (int i = labelCount; --i >= 0;) {
+				LabelInfo.setInstruction(currentLabel.get(i), insn);
+			}
+			currentLabel.clear();
+		}
+		if (currentInsn != null) {
+			currentInsn.addBranch(insn, 0);
+		}
+		currentInsn = insn;
+		instructions.put(node, insn);
+	}
+
+	/**
+	 * Declares that the next instruction will not be a successor of the current
+	 * instruction. This is the case with an unconditional jump or technically
+	 * when a probe was inserted before.
+	 */
+	void noSuccessor() {
+		currentInsn = null;
+	}
+
+	/**
+	 * Adds a jump from the last added instruction.
+	 * 
+	 * @param target
+	 *            jump target
+	 * @param branch
+	 *            unique branch number
+	 */
+	void addJump(final Label target, final int branch) {
+		jumps.add(new Jump(currentInsn, target, branch));
+	}
+
+	/**
+	 * Adds a new probe for the last instruction.
+	 * 
+	 * @param probeId
+	 *            index in the probe array
+	 * @param branch
+	 *            unique branch number for the last instruction
+	 */
+	void addProbe(final int probeId, final int branch) {
+		final boolean executed = probes != null && probes[probeId];
+		currentInsn.addBranch(executed, branch);
+	}
+
+	/**
+	 * Returns the status for all instructions of this method. This method must
+	 * be called exactly once after the instructions have been added.
+	 * 
+	 * @return map of ASM instruction nodes to corresponding {@link Instruction}
+	 *         instances
+	 */
+	Map<AbstractInsnNode, Instruction> getInstructions() {
+		// Wire jumps:
+		for (final Jump j : jumps) {
+			j.wire();
+		}
+
+		return instructions;
+	}
+
+	private static class Jump {
+
+		private final Instruction source;
+		private final Label target;
+		private final int branch;
+
+		Jump(final Instruction source, final Label target, final int branch) {
+			this.source = source;
+			this.target = target;
+			this.branch = branch;
+		}
+
+		void wire() {
+			source.addBranch(LabelInfo.getInstruction(target), branch);
+		}
+
+	}
+
+}
diff --git a/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodAnalyzer.java b/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodAnalyzer.java
index 78adf91a..b0c300f0 100644
--- a/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodAnalyzer.java
+++ b/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodAnalyzer.java
@@ -11,21 +11,7 @@
  *******************************************************************************/
 package org.jacoco.core.internal.analysis;
 
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.jacoco.core.analysis.ICounter;
-import org.jacoco.core.analysis.IMethodCoverage;
-import org.jacoco.core.analysis.ISourceNode;
-import org.jacoco.core.internal.analysis.filter.IFilter;
-import org.jacoco.core.internal.analysis.filter.IFilterContext;
-import org.jacoco.core.internal.analysis.filter.IFilterOutput;
 import org.jacoco.core.internal.flow.IFrame;
-import org.jacoco.core.internal.flow.Instruction;
 import org.jacoco.core.internal.flow.LabelInfo;
 import org.jacoco.core.internal.flow.MethodProbesVisitor;
 import org.objectweb.asm.Handle;
@@ -36,86 +22,26 @@ import org.objectweb.asm.tree.MethodNode;
 import org.objectweb.asm.tree.TryCatchBlockNode;
 
 /**
- * A {@link MethodProbesVisitor} that analyzes which statements and branches of
- * a method have been executed based on given probe data.
+ * A {@link MethodProbesVisitor} that builds the {@link Instruction}s of a
+ * method to calculate the detailed execution status.
  */
-public class MethodAnalyzer extends MethodProbesVisitor
-		implements IFilterOutput {
-
-	private final boolean[] probes;
-
-	private final IFilter filter;
-
-	private final IFilterContext filterContext;
-
-	private final MethodCoverageImpl coverage;
-
-	private int currentLine = ISourceNode.UNKNOWN_LINE;
-
-	private int firstLine = ISourceNode.UNKNOWN_LINE;
-
-	private int lastLine = ISourceNode.UNKNOWN_LINE;
-
-	// Due to ASM issue #315745 there can be more than one label per instruction
-	private final List<Label> currentLabel = new ArrayList<Label>(2);
-
-	/** List of all analyzed instructions */
-	private final List<Instruction> instructions = new ArrayList<Instruction>();
+public class MethodAnalyzer extends MethodProbesVisitor {
 
-	/** List of all predecessors of covered probes */
-	private final List<CoveredProbe> coveredProbes = new ArrayList<CoveredProbe>();
+	private final InstructionsBuilder builder;
 
-	/** List of all jumps encountered */
-	private final List<Jump> jumps = new ArrayList<Jump>();
-
-	/** Last instruction in byte code sequence */
-	private Instruction lastInsn;
-
-	/**
-	 * New Method analyzer for the given probe data.
-	 *
-	 * @param name
-	 *            method name
-	 * @param desc
-	 *            method descriptor
-	 * @param signature
-	 *            optional parameterized signature
-	 * @param probes
-	 *            recorded probe date of the containing class or
-	 *            <code>null</code> if the class is not executed at all
-	 * @param filter
-	 *            filter which should be applied
-	 * @param filterContext
-	 *            class context information for the filter
-	 */
-	MethodAnalyzer(final String name, final String desc, final String signature,
-			final boolean[] probes, final IFilter filter,
-			final IFilterContext filterContext) {
-		super();
-		this.probes = probes;
-		this.filter = filter;
-		this.filterContext = filterContext;
-		this.coverage = new MethodCoverageImpl(name, desc, signature);
-	}
+	/** Current node of the ASM tree API */
+	private AbstractInsnNode currentNode;
 
 	/**
-	 * Returns the coverage data for this method after this visitor has been
-	 * processed.
-	 * 
-	 * @return coverage data for this method
+	 * New instance that uses the given builder.
 	 */
-	public IMethodCoverage getCoverage() {
-		return coverage;
+	MethodAnalyzer(final InstructionsBuilder builder) {
+		this.builder = builder;
 	}
 
-	/**
-	 * {@link MethodNode#accept(MethodVisitor)}
-	 */
 	@Override
 	public void accept(final MethodNode methodNode,
 			final MethodVisitor methodVisitor) {
-		filter.filter(methodNode, filterContext, this);
-
 		methodVisitor.visitCode();
 		for (final TryCatchBlockNode n : methodNode.tryCatchBlocks) {
 			n.accept(methodVisitor);
@@ -128,146 +54,68 @@ public class MethodAnalyzer extends MethodProbesVisitor
 		methodVisitor.visitEnd();
 	}
 
-	private final Set<AbstractInsnNode> ignored = new HashSet<AbstractInsnNode>();
-
-	/**
-	 * Instructions that should be merged form disjoint sets. Coverage
-	 * information from instructions of one set will be merged into
-	 * representative instruction of set.
-	 * 
-	 * Each such set is represented as a singly linked list: each element except
-	 * one references another element from the same set, element without
-	 * reference - is a representative of this set.
-	 * 
-	 * This map stores reference (value) for elements of sets (key).
-	 */
-	private final Map<AbstractInsnNode, AbstractInsnNode> merged = new HashMap<AbstractInsnNode, AbstractInsnNode>();
-
-	private final Map<AbstractInsnNode, Instruction> nodeToInstruction = new HashMap<AbstractInsnNode, Instruction>();
-
-	private AbstractInsnNode currentNode;
-
-	public void ignore(final AbstractInsnNode fromInclusive,
-			final AbstractInsnNode toInclusive) {
-		for (AbstractInsnNode i = fromInclusive; i != toInclusive; i = i
-				.getNext()) {
-			ignored.add(i);
-		}
-		ignored.add(toInclusive);
-	}
-
-	private AbstractInsnNode findRepresentative(AbstractInsnNode i) {
-		AbstractInsnNode r = merged.get(i);
-		while (r != null) {
-			i = r;
-			r = merged.get(i);
-		}
-		return i;
-	}
-
-	public void merge(AbstractInsnNode i1, AbstractInsnNode i2) {
-		i1 = findRepresentative(i1);
-		i2 = findRepresentative(i2);
-		if (i1 != i2) {
-			merged.put(i2, i1);
-		}
-	}
-
-	private final Map<AbstractInsnNode, Set<AbstractInsnNode>> replacements = new HashMap<AbstractInsnNode, Set<AbstractInsnNode>>();
-
-	public void replaceBranches(final AbstractInsnNode source,
-			final Set<AbstractInsnNode> newTargets) {
-		replacements.put(source, newTargets);
-	}
-
 	@Override
 	public void visitLabel(final Label label) {
-		currentLabel.add(label);
-		if (!LabelInfo.isSuccessor(label)) {
-			lastInsn = null;
-		}
+		builder.addLabel(label);
 	}
 
 	@Override
 	public void visitLineNumber(final int line, final Label start) {
-		currentLine = line;
-		if (firstLine > line || lastLine == ISourceNode.UNKNOWN_LINE) {
-			firstLine = line;
-		}
-		if (lastLine < line) {
-			lastLine = line;
-		}
-	}
-
-	private void visitInsn() {
-		final Instruction insn = new Instruction(currentNode, currentLine);
-		nodeToInstruction.put(currentNode, insn);
-		instructions.add(insn);
-		if (lastInsn != null) {
-			insn.setPredecessor(lastInsn, 0);
-		}
-		final int labelCount = currentLabel.size();
-		if (labelCount > 0) {
-			for (int i = labelCount; --i >= 0;) {
-				LabelInfo.setInstruction(currentLabel.get(i), insn);
-			}
-			currentLabel.clear();
-		}
-		lastInsn = insn;
+		builder.setCurrentLine(line);
 	}
 
 	@Override
 	public void visitInsn(final int opcode) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitIntInsn(final int opcode, final int operand) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitVarInsn(final int opcode, final int var) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitTypeInsn(final int opcode, final String type) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitFieldInsn(final int opcode, final String owner,
 			final String name, final String desc) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitMethodInsn(final int opcode, final String owner,
 			final String name, final String desc, final boolean itf) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitInvokeDynamicInsn(final String name, final String desc,
 			final Handle bsm, final Object... bsmArgs) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitJumpInsn(final int opcode, final Label label) {
-		visitInsn();
-		jumps.add(new Jump(lastInsn, label, 1));
+		builder.addInstruction(currentNode);
+		builder.addJump(label, 1);
 	}
 
 	@Override
 	public void visitLdcInsn(final Object cst) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitIincInsn(final int var, final int increment) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
@@ -283,15 +131,15 @@ public class MethodAnalyzer extends MethodProbesVisitor
 	}
 
 	private void visitSwitchInsn(final Label dflt, final Label[] labels) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 		LabelInfo.resetDone(labels);
 		int branch = 0;
-		jumps.add(new Jump(lastInsn, dflt, branch));
+		builder.addJump(dflt, branch);
 		LabelInfo.setDone(dflt);
 		for (final Label l : labels) {
 			if (!LabelInfo.isDone(l)) {
 				branch++;
-				jumps.add(new Jump(lastInsn, l, branch));
+				builder.addJump(l, branch);
 				LabelInfo.setDone(l);
 			}
 		}
@@ -299,26 +147,26 @@ public class MethodAnalyzer extends MethodProbesVisitor
 
 	@Override
 	public void visitMultiANewArrayInsn(final String desc, final int dims) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 	}
 
 	@Override
 	public void visitProbe(final int probeId) {
-		addProbe(probeId, 0);
-		lastInsn = null;
+		builder.addProbe(probeId, 0);
+		builder.noSuccessor();
 	}
 
 	@Override
 	public void visitJumpInsnWithProbe(final int opcode, final Label label,
 			final int probeId, final IFrame frame) {
-		visitInsn();
-		addProbe(probeId, 1);
+		builder.addInstruction(currentNode);
+		builder.addProbe(probeId, 1);
 	}
 
 	@Override
 	public void visitInsnWithProbe(final int opcode, final int probeId) {
-		visitInsn();
-		addProbe(probeId, 0);
+		builder.addInstruction(currentNode);
+		builder.addProbe(probeId, 0);
 	}
 
 	@Override
@@ -335,7 +183,7 @@ public class MethodAnalyzer extends MethodProbesVisitor
 
 	private void visitSwitchInsnWithProbes(final Label dflt,
 			final Label[] labels) {
-		visitInsn();
+		builder.addInstruction(currentNode);
 		LabelInfo.resetDone(dflt);
 		LabelInfo.resetDone(labels);
 		int branch = 0;
@@ -350,108 +198,12 @@ public class MethodAnalyzer extends MethodProbesVisitor
 		final int id = LabelInfo.getProbeId(label);
 		if (!LabelInfo.isDone(label)) {
 			if (id == LabelInfo.NO_PROBE) {
-				jumps.add(new Jump(lastInsn, label, branch));
+				builder.addJump(label, branch);
 			} else {
-				addProbe(id, branch);
+				builder.addProbe(id, branch);
 			}
 			LabelInfo.setDone(label);
 		}
 	}
 
-	@Override
-	public void visitEnd() {
-		// Wire jumps:
-		for (final Jump j : jumps) {
-			LabelInfo.getInstruction(j.target).setPredecessor(j.source,
-					j.branch);
-		}
-		// Propagate probe values:
-		for (final CoveredProbe p : coveredProbes) {
-			p.instruction.setCovered(p.branch);
-		}
-
-		// Merge into representative instruction:
-		for (final Instruction i : instructions) {
-			final AbstractInsnNode m = i.getNode();
-			final AbstractInsnNode r = findRepresentative(m);
-			if (r != m) {
-				ignored.add(m);
-				nodeToInstruction.get(r).merge(i);
-			}
-		}
-
-		// Merge from representative instruction, because result of merge might
-		// be used to compute coverage of instructions with replaced branches:
-		for (final Instruction i : instructions) {
-			final AbstractInsnNode m = i.getNode();
-			final AbstractInsnNode r = findRepresentative(m);
-			if (r != m) {
-				i.merge(nodeToInstruction.get(r));
-			}
-		}
-
-		// Report result:
-		coverage.ensureCapacity(firstLine, lastLine);
-		for (final Instruction i : instructions) {
-			if (ignored.contains(i.getNode())) {
-				continue;
-			}
-
-			final int total;
-			final int covered;
-			final Set<AbstractInsnNode> r = replacements.get(i.getNode());
-			if (r != null) {
-				int cb = 0;
-				for (AbstractInsnNode b : r) {
-					if (nodeToInstruction.get(b).getCoveredBranches() > 0) {
-						cb++;
-					}
-				}
-				total = r.size();
-				covered = cb;
-			} else {
-				total = i.getBranches();
-				covered = i.getCoveredBranches();
-			}
-
-			final ICounter instrCounter = covered == 0 ? CounterImpl.COUNTER_1_0
-					: CounterImpl.COUNTER_0_1;
-			final ICounter branchCounter = total > 1
-					? CounterImpl.getInstance(total - covered, covered)
-					: CounterImpl.COUNTER_0_0;
-			coverage.increment(instrCounter, branchCounter, i.getLine());
-		}
-		coverage.incrementMethodCounter();
-	}
-
-	private void addProbe(final int probeId, final int branch) {
-		lastInsn.addBranch();
-		if (probes != null && probes[probeId]) {
-			coveredProbes.add(new CoveredProbe(lastInsn, branch));
-		}
-	}
-
-	private static class CoveredProbe {
-		final Instruction instruction;
-		final int branch;
-
-		private CoveredProbe(final Instruction instruction, final int branch) {
-			this.instruction = instruction;
-			this.branch = branch;
-		}
-	}
-
-	private static class Jump {
-
-		final Instruction source;
-		final Label target;
-		final int branch;
-
-		Jump(final Instruction source, final Label target, final int branch) {
-			this.source = source;
-			this.target = target;
-			this.branch = branch;
-		}
-	}
-
 }
diff --git a/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodCoverageCalculator.java b/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodCoverageCalculator.java
new file mode 100644
index 00000000..e2dba779
--- /dev/null
+++ b/org.jacoco.core/src/org/jacoco/core/internal/analysis/MethodCoverageCalculator.java
@@ -0,0 +1,178 @@
+/*******************************************************************************
+ * Copyright (c) 2009, 2018 Mountainminds GmbH & Co. KG and Contributors
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *    Evgeny Mandrikov - initial API and implementation
+ *    
+ *******************************************************************************/
+package org.jacoco.core.internal.analysis;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import org.jacoco.core.analysis.ISourceFileCoverage;
+import org.jacoco.core.analysis.ISourceNode;
+import org.jacoco.core.internal.analysis.filter.IFilterOutput;
+import org.objectweb.asm.tree.AbstractInsnNode;
+
+/**
+ * Calculates the filtered coverage of a single method. A instance of this class
+ * can be first used as {@link IFilterOutput} before the coverage result is
+ * calculated.
+ */
+class MethodCoverageCalculator implements IFilterOutput {
+
+	private final Map<AbstractInsnNode, Instruction> instructions;
+
+	private final Set<AbstractInsnNode> ignored;
+
+	/**
+	 * Instructions that should be merged form disjoint sets. Coverage
+	 * information from instructions of one set will be merged into
+	 * representative instruction of set.
+	 * 
+	 * Each such set is represented as a singly linked list: each element except
+	 * one references another element from the same set, element without
+	 * reference - is a representative of this set.
+	 * 
+	 * This map stores reference (value) for elements of sets (key).
+	 */
+	private final Map<AbstractInsnNode, AbstractInsnNode> merged;
+
+	private final Map<AbstractInsnNode, Set<AbstractInsnNode>> replacements;
+
+	MethodCoverageCalculator(
+			final Map<AbstractInsnNode, Instruction> instructions) {
+		this.instructions = instructions;
+		this.ignored = new HashSet<AbstractInsnNode>();
+		this.merged = new HashMap<AbstractInsnNode, AbstractInsnNode>();
+		this.replacements = new HashMap<AbstractInsnNode, Set<AbstractInsnNode>>();
+	}
+
+	/**
+	 * Applies all specified filtering commands and calculates the resulting
+	 * coverage.
+	 * 
+	 * @param coverage
+	 *            the result is added to this coverage node
+	 */
+	void calculate(final MethodCoverageImpl coverage) {
+		applyMerges();
+		applyReplacements();
+		ensureCapacity(coverage);
+
+		for (final Entry<AbstractInsnNode, Instruction> entry : instructions
+				.entrySet()) {
+			if (!ignored.contains(entry.getKey())) {
+				final Instruction instruction = entry.getValue();
+				coverage.increment(instruction.getInstructionCounter(),
+						instruction.getBranchCounter(), instruction.getLine());
+			}
+		}
+
+		coverage.incrementMethodCounter();
+	}
+
+	private void applyMerges() {
+		// Merge to the representative:
+		for (final Entry<AbstractInsnNode, AbstractInsnNode> entry : merged
+				.entrySet()) {
+			final AbstractInsnNode node = entry.getKey();
+			final Instruction instruction = instructions.get(node);
+			final AbstractInsnNode representativeNode = findRepresentative(
+					node);
+			ignored.add(node);
+			instructions.put(representativeNode,
+					instructions.get(representativeNode).merge(instruction));
+			entry.setValue(representativeNode);
+		}
+
+		// Get merged value back from representative
+		for (final Entry<AbstractInsnNode, AbstractInsnNode> entry : merged
+				.entrySet()) {
+			instructions.put(entry.getKey(),
+					instructions.get(entry.getValue()));
+		}
+	}
+
+	private void applyReplacements() {
+		for (final Entry<AbstractInsnNode, Set<AbstractInsnNode>> entry : replacements
+				.entrySet()) {
+			final Set<AbstractInsnNode> replacements = entry.getValue();
+			final List<Instruction> newBranches = new ArrayList<Instruction>(
+					replacements.size());
+			for (final AbstractInsnNode b : replacements) {
+				newBranches.add(instructions.get(b));
+			}
+			final AbstractInsnNode node = entry.getKey();
+			instructions.put(node,
+					instructions.get(node).replaceBranches(newBranches));
+		}
+	}
+
+	private void ensureCapacity(final MethodCoverageImpl coverage) {
+		// Determine line range:
+		int firstLine = ISourceFileCoverage.UNKNOWN_LINE;
+		int lastLine = ISourceFileCoverage.UNKNOWN_LINE;
+		for (final Entry<AbstractInsnNode, Instruction> entry : instructions
+				.entrySet()) {
+			if (!ignored.contains(entry.getKey())) {
+				final int line = entry.getValue().getLine();
+				if (line != ISourceNode.UNKNOWN_LINE) {
+					if (firstLine > line
+							|| lastLine == ISourceNode.UNKNOWN_LINE) {
+						firstLine = line;
+					}
+					if (lastLine < line) {
+						lastLine = line;
+					}
+				}
+			}
+		}
+
+		// Performance optimization to avoid incremental increase of line array:
+		coverage.ensureCapacity(firstLine, lastLine);
+	}
+
+	private AbstractInsnNode findRepresentative(AbstractInsnNode i) {
+		AbstractInsnNode r;
+		while ((r = merged.get(i)) != null) {
+			i = r;
+		}
+		return i;
+	}
+
+	// === IFilterOutput API ===
+
+	public void ignore(final AbstractInsnNode fromInclusive,
+			final AbstractInsnNode toInclusive) {
+		for (AbstractInsnNode i = fromInclusive; i != toInclusive; i = i
+				.getNext()) {
+			ignored.add(i);
+		}
+		ignored.add(toInclusive);
+	}
+
+	public void merge(AbstractInsnNode i1, AbstractInsnNode i2) {
+		i1 = findRepresentative(i1);
+		i2 = findRepresentative(i2);
+		if (i1 != i2) {
+			merged.put(i2, i1);
+		}
+	}
+
+	public void replaceBranches(final AbstractInsnNode source,
+			final Set<AbstractInsnNode> newTargets) {
+		replacements.put(source, newTargets);
+	}
+
+}
diff --git a/org.jacoco.core/src/org/jacoco/core/internal/flow/Instruction.java b/org.jacoco.core/src/org/jacoco/core/internal/flow/Instruction.java
deleted file mode 100644
index d1e7cbeb..00000000
--- a/org.jacoco.core/src/org/jacoco/core/internal/flow/Instruction.java
+++ /dev/null
@@ -1,149 +0,0 @@
-/*******************************************************************************
- * Copyright (c) 2009, 2018 Mountainminds GmbH & Co. KG and Contributors
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License v1.0
- * which accompanies this distribution, and is available at
- * http://www.eclipse.org/legal/epl-v10.html
- *
- * Contributors:
- *    Marc R. Hoffmann - initial API and implementation
- *    
- *******************************************************************************/
-package org.jacoco.core.internal.flow;
-
-import org.objectweb.asm.tree.AbstractInsnNode;
-
-import java.util.BitSet;
-
-/**
- * Representation of a byte code instruction for analysis. Internally used for
- * analysis.
- */
-public class Instruction {
-
-	private final AbstractInsnNode node;
-
-	private final int line;
-
-	private int branches;
-
-	private final BitSet coveredBranches;
-
-	private Instruction predecessor;
-
-	private int predecessorBranch;
-
-	/**
-	 * New instruction at the given line.
-	 * 
-	 * @param node
-	 *            corresponding node
-	 * @param line
-	 *            source line this instruction belongs to
-	 */
-	public Instruction(final AbstractInsnNode node, final int line) {
-		this.node = node;
-		this.line = line;
-		this.branches = 0;
-		this.coveredBranches = new BitSet();
-	}
-
-	/**
-	 * @return corresponding node
-	 */
-	public AbstractInsnNode getNode() {
-		return node;
-	}
-
-	/**
-	 * Adds an branch to this instruction.
-	 */
-	public void addBranch() {
-		branches++;
-	}
-
-	/**
-	 * Sets the given instruction as a predecessor of this instruction and adds
-	 * branch to the predecessor. Probes are inserted in a way that every
-	 * instruction has at most one direct predecessor.
-	 * 
-	 * @see #addBranch()
-	 * @param predecessor
-	 *            predecessor instruction
-	 * @param branch
-	 *            branch number in predecessor that should be marked as covered
-	 *            when this instruction marked as covered
-	 */
-	public void setPredecessor(final Instruction predecessor,
-			final int branch) {
-		this.predecessor = predecessor;
-		predecessor.addBranch();
-		this.predecessorBranch = branch;
-	}
-
-	/**
-	 * Marks one branch of this instruction as covered. Also recursively marks
-	 * all predecessor instructions as covered if this is the first covered
-	 * branch.
-	 *
-	 * @param branch
-	 *            branch number to mark as covered
-	 */
-	public void setCovered(final int branch) {
-		Instruction i = this;
-		int b = branch;
-		while (i != null) {
-			if (!i.coveredBranches.isEmpty()) {
-				i.coveredBranches.set(b);
-				break;
-			}
-			i.coveredBranches.set(b);
-			b = i.predecessorBranch;
-			i = i.predecessor;
-		}
-	}
-
-	/**
-	 * Returns the source line this instruction belongs to.
-	 * 
-	 * @return corresponding source line
-	 */
-	public int getLine() {
-		return line;
-	}
-
-	/**
-	 * Returns the total number of branches starting from this instruction.
-	 * 
-	 * @return total number of branches
-	 */
-	public int getBranches() {
-		return branches;
-	}
-
-	/**
-	 * Returns the number of covered branches starting from this instruction.
-	 * 
-	 * @return number of covered branches
-	 */
-	public int getCoveredBranches() {
-		return coveredBranches.cardinality();
-	}
-
-	/**
-	 * Merges information about covered branches of given instruction into this
-	 * instruction.
-	 * 
-	 * @param instruction
-	 *            instruction from which to merge
-	 */
-	public void merge(Instruction instruction) {
-		this.coveredBranches.or(instruction.coveredBranches);
-	}
-
-	@Override
-	public String toString() {
-		return coveredBranches.toString();
-	}
-
-}
diff --git a/org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java b/org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java
index 1b65ae2a..56b392d0 100644
--- a/org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java
+++ b/org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java
@@ -11,6 +11,7 @@
  *******************************************************************************/
 package org.jacoco.core.internal.flow;
 
+import org.jacoco.core.internal.analysis.Instruction;
 import org.objectweb.asm.Label;
 
 /**