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