Control dependency

Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.
An instruction B has a control dependency on a preceding instruction A if the outcome of A determines whether B should be executed or not. In the following example, the instruction 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 has a control dependency on instruction 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
. However, 
 
 
 
 
 S
 
 3
 
 
 
 
 {\displaystyle S_{3}}
 
 does not depend on 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
 because 
 
 
 
 
 S
 
 3
 
 
 
 
 {\displaystyle S_{3}}
 
 is always executed irrespective of the outcome of 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
.

S1. if (a == b)
S2. a = a + b
S3. b = a + b

Intuitively, there is control dependence between two statements A and B if

<ul><li>B could be possibly executed after A</li>
<li>The outcome of the execution of A will determine whether B will be executed or not.</li></ul>
A typical example is that there are control dependences between the condition part of an if statement and the statements in its true/false bodies.
A formal definition of control dependence can be presented as follows:
A statement 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 is said to be control dependent on another statement 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
 <a href="/facts/If_and_only_if/bYSxGJ66">iff</a>

<ul><li>there exists a path 
 
 
 
 P
 
 
 {\displaystyle P}
 
 from 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
 to 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 such that every statement 
 
 
 
 
 S
 
 i
 
 
 
 
 {\displaystyle S_{i}}
 
 ≠ 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
 within 
 
 
 
 P
 
 
 {\displaystyle P}
 
 will be followed by 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 in each possible path to the end of the program and</li>
<li>
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
 will not necessarily be followed by 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
, i.e. there is an execution path from 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
 to the end of the program that does not go through 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
.</li></ul>
Expressed with the help of (post-)dominance the two conditions are equivalent to

<ul><li>
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 post-dominates all 
 
 
 
 
 S
 
 i
 
 
 
 
 {\displaystyle S_{i}}
 
</li>
<li>
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 does not post-dominate 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
</li></ul>

Control dependency open-in-new

Control dependency