Instrument edges instead of basic blocks

We are currently deriving edge coverage instrumentation from basic block
instrumentation via the AFL XOR-technique. This has several downsides:

* Different edges can be assigned the same position in the coverage map,
  which leads to underreported coverage.
* The coverage map needs to be large enough for collisions to be
  unlikely (on the order of num_edges^2). In addition to being wasteful,
  it is also hard to determine the correct size given that we don't know
  the number of edges.

In addition to the design limitations, the current implementation
additionally does not take into account that most Java method
invocations can throw exceptions and thus need to be instrumented.

These issues are resolved by switching to true LLVM-style edge coverage
instrumentation. The new coverage instrumentation is based on a lightly
patched version of the JaCoCo internals.

Note:
//agent/src/test/java/com/code_intelligence/jazzer/instrumentor:coverage_instrumentation_test
is not passing for this commit. It will be fixed with the next commit.

3 files changed, 140 insertions, 0 deletions

diff --git a/third_party/BUILD.bazel b/third_party/BUILD.bazel
index e4e22821..fd65eb9b 100644
--- a/third_party/BUILD.bazel
+++ b/third_party/BUILD.bazel
@@ -1,4 +1,6 @@
 exports_files([
     "gflags-use-double-dash-args.patch",
+    "jacoco-make-probe-inserter-subclassable.patch",
+    "jacoco_internal.BUILD",
     "libjpeg_turbo.BUILD",
 ])
diff --git a/third_party/jacoco-make-probe-inserter-subclassable.patch b/third_party/jacoco-make-probe-inserter-subclassable.patch
new file mode 100644
index 00000000..6191a00f
--- /dev/null
+++ b/third_party/jacoco-make-probe-inserter-subclassable.patch
@@ -0,0 +1,123 @@
+// SPDX-License-Identifier: EPL-2.0 and Apache-2.0
+// These patches apply to JaCoCo (https://github.com/jacoco/jacoco) and are hereby made available under the terms of the
+// Eclipse Public License 2.0 available at:
+//   http://www.eclipse.org/legal/epl-2.0
+diff --git org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java
+index 122d62b5..5ba3cf8d 100644
+--- org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java
++++ org.jacoco.core/src/org/jacoco/core/internal/flow/LabelInfo.java
+@@ -141,8 +141,7 @@ public final class LabelInfo {
+ 	 */
+ 	public static boolean needsProbe(final Label label) {
+ 		final LabelInfo info = get(label);
+-		return info != null && info.successor
+-				&& (info.multiTarget || info.methodInvocationLine);
++		return info != null && info.successor && info.multiTarget;
+ 	}
+ 
+ 	/**
+diff --git org.jacoco.core/src/org/jacoco/core/internal/instr/ClassInstrumenter.java org.jacoco.core/src/org/jacoco/core/internal/instr/ClassInstrumenter.java
+index 476c9e34..bc192dc6 100644
+--- org.jacoco.core/src/org/jacoco/core/internal/instr/ClassInstrumenter.java
++++ org.jacoco.core/src/org/jacoco/core/internal/instr/ClassInstrumenter.java
+@@ -24,6 +24,7 @@ import org.objectweb.asm.MethodVisitor;
+ public class ClassInstrumenter extends ClassProbesVisitor {
+ 
+ 	private final IProbeArrayStrategy probeArrayStrategy;
++	private final IProbeInserterFactory probeInserterFactory;
+ 
+ 	private String className;
+ 
+@@ -40,6 +41,22 @@ public class ClassInstrumenter extends ClassProbesVisitor {
+ 			final ClassVisitor cv) {
+ 		super(cv);
+ 		this.probeArrayStrategy = probeArrayStrategy;
++		this.probeInserterFactory = new IProbeInserterFactory() {
++			@Override
++			public ProbeInserter makeProbeInserter(int access, String name,
++					String desc, MethodVisitor mv,
++					IProbeArrayStrategy arrayStrategy) {
++				return new ProbeInserter(access, name, desc, mv, arrayStrategy);
++			}
++		};
++	}
++
++	public ClassInstrumenter(final IProbeArrayStrategy probeArrayStrategy,
++			final IProbeInserterFactory probeInserterFactory,
++			final ClassVisitor cv) {
++		super(cv);
++		this.probeArrayStrategy = probeArrayStrategy;
++		this.probeInserterFactory = probeInserterFactory;
+ 	}
+ 
+ 	@Override
+@@ -71,8 +88,9 @@ public class ClassInstrumenter extends ClassProbesVisitor {
+ 			return null;
+ 		}
+ 		final MethodVisitor frameEliminator = new DuplicateFrameEliminator(mv);
+-		final ProbeInserter probeVariableInserter = new ProbeInserter(access,
+-				name, desc, frameEliminator, probeArrayStrategy);
++		final ProbeInserter probeVariableInserter =
++				probeInserterFactory.makeProbeInserter(access, name, desc,
++						frameEliminator, probeArrayStrategy);
+ 		return new MethodInstrumenter(probeVariableInserter,
+ 				probeVariableInserter);
+ 	}
+diff --git org.jacoco.core/src/org/jacoco/core/internal/instr/IProbeInserterFactory.java org.jacoco.core/src/org/jacoco/core/internal/instr/IProbeInserterFactory.java
+new file mode 100644
+index 00000000..19c2a7e2
+--- /dev/null
++++ org.jacoco.core/src/org/jacoco/core/internal/instr/IProbeInserterFactory.java
+@@ -0,0 +1,8 @@
++package org.jacoco.core.internal.instr;
++
++import org.objectweb.asm.MethodVisitor;
++
++public interface IProbeInserterFactory {
++    ProbeInserter makeProbeInserter(int access, String name, String desc,
++            MethodVisitor mv, IProbeArrayStrategy arrayStrategy);
++}
+diff --git org.jacoco.core/src/org/jacoco/core/internal/instr/InstrSupport.java org.jacoco.core/src/org/jacoco/core/internal/instr/InstrSupport.java
+index 71808ac8..3df93f63 100644
+--- org.jacoco.core/src/org/jacoco/core/internal/instr/InstrSupport.java
++++ org.jacoco.core/src/org/jacoco/core/internal/instr/InstrSupport.java
+@@ -78,7 +78,7 @@ public final class InstrSupport {
+ 	 * Data type of the field that stores coverage information for a class (
+ 	 * <code>boolean[]</code>).
+ 	 */
+-	public static final String DATAFIELD_DESC = "[Z";
++	public static final String DATAFIELD_DESC = "java/nio/ByteBuffer";
+ 
+ 	// === Init Method ===
+ 
+diff --git org.jacoco.core/src/org/jacoco/core/internal/instr/ProbeInserter.java org.jacoco.core/src/org/jacoco/core/internal/instr/ProbeInserter.java
+index 0f5b99ff..ba5daa6d 100644
+--- org.jacoco.core/src/org/jacoco/core/internal/instr/ProbeInserter.java
++++ org.jacoco.core/src/org/jacoco/core/internal/instr/ProbeInserter.java
+@@ -25,7 +25,7 @@ import org.objectweb.asm.TypePath;
+  * addition the probe array has to be retrieved at the beginning of the method
+  * and stored in a local variable.
+  */
+-class ProbeInserter extends MethodVisitor implements IProbeInserter {
++public class ProbeInserter extends MethodVisitor implements IProbeInserter {
+ 
+ 	private final IProbeArrayStrategy arrayStrategy;
+ 
+@@ -36,7 +36,7 @@ class ProbeInserter extends MethodVisitor implements IProbeInserter {
+ 	private final boolean clinit;
+ 
+ 	/** Position of the inserted variable. */
+-	private final int variable;
++	protected final int variable;
+ 
+ 	/** Maximum stack usage of the code to access the probe array. */
+ 	private int accessorStackSize;
+@@ -56,7 +56,7 @@ class ProbeInserter extends MethodVisitor implements IProbeInserter {
+ 	 *            callback to create the code that retrieves the reference to
+ 	 *            the probe array
+ 	 */
+-	ProbeInserter(final int access, final String name, final String desc,
++	public ProbeInserter(final int access, final String name, final String desc,
+ 			final MethodVisitor mv, final IProbeArrayStrategy arrayStrategy) {
+ 		super(InstrSupport.ASM_API_VERSION, mv);
+ 		this.clinit = InstrSupport.CLINIT_NAME.equals(name);
diff --git a/third_party/jacoco_internal.BUILD b/third_party/jacoco_internal.BUILD
new file mode 100644
index 00000000..586f8a25
--- /dev/null
+++ b/third_party/jacoco_internal.BUILD
@@ -0,0 +1,15 @@
+java_library(
+    name = "jacoco_internal",
+    srcs = glob([
+        "org.jacoco.core/src/org/jacoco/core/**/*.java",
+    ]),
+    javacopts = [
+        "-Xep:EqualsHashCode:WARN",
+    ],
+    deps = [
+        "@maven//:org_ow2_asm_asm",
+        "@maven//:org_ow2_asm_asm_commons",
+        "@maven//:org_ow2_asm_asm_tree",
+    ],
+    visibility = ["//visibility:public"],
+)