Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / jacoco / 102e8373a4b3a046786fd2ef9b55c9729215ee72 / . / org.jacoco.doc / docroot / doc / flow.html
blob: e207d85fa0bcd553887264e1eca9d88426ec21ed [file] [log] [blame]
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]1<?xml version="1.0" encoding="ISO-8859-1" ?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
4<head>
5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
6 <link rel="stylesheet" href=".resources/doc.css" charset="ISO-8859-1" type="text/css" />
7 <title>JaCoCo - Control Flow Analysis</title>
8</head>
9<body>
10
11<div class="breadcrumb">
12 <a href="../index.html" class="el_session">JaCoCo</a> &gt;
13 <a href="index.html" class="el_group">Documentation</a> &gt;
14 <span class="el_source">Control Flow Analysis</span>
15</div>
16<div id="content">
17
18<h1>Control Flow Analysis for Java Methods</h1>
19
20<p style="font-weight:bold;">
21 DRAFT - This document does not reflect the current JaCoCo implementation.
22</p>
23
24<p class="hint">
25 Implementing a coverage tool for branch coverage requires detailed analysis
26 of the internal control flow of Java methods. Due to the architecture of
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame^]27 JaCoCo this analysis needs to happen on compiled class files (bytecode).
28 This document defines graph structures for control flow analysis of Java
29 bytecode and discusses strategies for probe insertion.
30 Marc R. Hoffmann, April 2010
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]31</p>
32
33<h2>Motivation and Requirements</h2>
34
35<ul>
36 <li>Path Coverage</li>
37 <li>Exception Detection</li>
38</ul>
39
40<h2>The Control Flow Graph</h2>
41
42<ul>
43 <li>Virtual Entry and Exit Nodes</li>
44 <li>Subsequent Instructions</li>
45 <li>(Conditional) Jump</li>
46 <li>Table/Lookup Switch</li>
47 <li>Exception Handlers</li>
48 <li>Unhandled Exceptions</li>
49</ul>
50
51<h2>Probe Insertion</h2>
52
53<p>
54 Code coverage analysis is a runtime metric that provides execution details
55 of the software under test. This requires detailed recording about the
56 instructions (instruction coverage) that have been executed. For path coverage
57 also the outcome of decisions has to be recorded. In any case execution data
58 is collected by so called probes:
59</p>
60
61<p class="hint">
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame^]62 A <b>probe</b> is a sequence of bytecode instructions that can be inserted
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]63 into a Java method. When the probe is executed, this fact is recorded and can
64 be reported by the coverage runtime.
65</p>
66
67<p>
68 The only purpose of the probe is to record that it has been executed at least
69 once. The probe does not record the number of times it has been called or
70 collect any timing information. The latter is out of scope for code coverage
71 analysis and more in the objective of a performance analysis tool. Typically
72 multiple probes needs to be inserted into each method, therefore probes needs
73 to be identified. Also the probe implementation and the storage mechanism it
74 depends on needs to be thread safe as multi-threaded execution is a common
75 scenario for java applications (albeit not for plain unit tests). Probes must
76 not have any side effects on the original code of the method. Also they should
77 add minimal overhead.
78</p>
79
80<p>
81 So to summarize the requirements for execution probes:
82</p>
83
84<ul>
85 <li>Record execution</li>
86 <li>Identification for different probes</li>
87 <li>Thread safe</li>
88 <li>No side effects on application code</li>
89 <li>Minimal runtime overhead</li>
90</ul>
91
92<p>
93 JaCoCo implements probes with a <code>boolean[]</code> array instance per
94 class. Each probe corresponds to a entry in this array. Whenever the probe is
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame^]95 executed the entry is set to <code>true</code> with the following four
96 bytecode instructions:
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]97</p>
98
99<pre class="source">
100ALOAD probearray
101xPUSH probeid
102ICONST_1
103BASTORE
104</pre>
105
106<p>
107 Note that this probe code is thread safe, does not modify the operand stack
108 or modify local variables and is also thread safe. It does also not leave the
109 method though an external call. The only prerequisite is that the probe array
110 is available as a local variable. For this at the beginning of each method
111 additional instrumentation code needs to be added to obtain the array instance
112 associated with the belonging class (to avoid code duplication the
113 initialization is delegated to a method <code>$jacocoinit()</code> which is
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame^]114 added to every non-interface class).
115</p>
116
117<p>
118 The size of the probe code above depends on the position of the probe array
119 variable and the value of the probe identifier as different opcodes can be
120 used. As calculated in the table below the overhead per probe ranges between 4
121 and 7 bytes of additional bytecode:
122</p>
123
124<table class="coverage">
125 <thead>
126 <tr>
127 <td>Possible Opcodes</td>
128 <td>Min. Size [bytes]</td>
129 <td>Max. Size [bytes]</td>
130 <td>Comment</td>
131 </tr>
132 </thead>
133 <tbody>
134 <tr>
135 <td><code>ALOAD_x</code>, <code>ALOAD</code></td>
136 <td>1</td>
137 <td>2</td>
138 <td>(1)</td>
139 </tr>
140 <tr>
141 <td><code>ICONST_x</code>, <code>BIPUSH</code>, <code>SIPUSH</code>, <code>LDC</code>, <code>LDC_W</code></td>
142 <td>1</td>
143 <td>3</td>
144 <td>(2)</td>
145 </tr>
146 <tr>
147 <td><code>ICONST_1</code></td>
148 <td>1</td>
149 <td>1</td>
150 <td></td>
151 </tr>
152 <tr>
153 <td><code>BASTORE</code></td>
154 <td>1</td>
155 <td>1</td>
156 <td></td>
157 </tr>
158 </tbody>
159 <tfoot>
160 <tr>
161 <td>Total:</td>
162 <td>4</td>
163 <td>7</td>
164 <td></td>
165 </tr>
166 </tfoot>
167</table>
168
169<p>
170 (1) The probe array is the first variable after the arguments. If the method
171 arguments do not consume more that 3 slots the 1-byte opcode can be used.<br/>
172 (2) 1-byte opcodes for ids 0 to 5, 2-byte opcode for ids up to 127, 3-byte opcode
173 for ids up to 32767. Ids values of 32768 or more require an additional
174 constant pool entry. For normal class files it is very unlikely to require
175 more than 32,000 probes.
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]176</p>
177
178<ul>
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]179 <li>Limitation: Only proves that the probe itself has been executed,
180 assumptions about the surrounding application code is interpolation</li>
181 <li>Probe in every edge of the control flow graph</li>
182 <li>Every exit path known (branch coverage)</li>
183 <li>Block entry known (exceptions within blocks)</li>
184</ul>
185
186<h2>Different Types of Edges</h2>
187
188<ul>
189 <li>Probe insertion strategies</li>
190</ul>
191
192<h2>Runtime Overhead</h2>
193
194<ul>
195 <li>Comparison to current basic block probes</li>
196</ul>
197
198</div>
199<div class="footer">
200 <div class="versioninfo"><a href="@jacoco.home.url@">JaCoCo</a> @qualified.bundle.version@</div>
201 <a href="license.html">Copyright</a> &copy; @copyright.years@ Mountainminds GmbH &amp; Co. KG and Contributors
202</div>
203
204</body>
205</html>