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 has a control dependency on instruction S_1 . However, S_3 does not depend on S_1 because S_3 is always executed irrespective of the outcome of 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 * B could be possibly executed after A * The outcome of the execution of A will determine whether B will be executed or not. 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 is said to be control dependent on another statement S_1 iff * there exists a path P from S_1 to S_2 such that every statement S_i ≠ S_1 within P will be followed by S_2 in each possible path to the end of the program and * S_1 will not necessarily be followed by S_2 , i.e. there is an execution path from S_1 to the end of the program that does not go through S_2 .…

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 has a control dependency on instruction S_1 . However, S_3 does not depend on S_1 because S_3 is always executed irrespective of the outcome of 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 B could be possibly executed after A The outcome of the execution of A will determine whether B will be executed or not. 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 is said to be control dependent on another statement S_1 iff there exists a path P from S_1 to S_2 such that every statement S_i ≠ S_1 within P will be followed by S_2 in each possible path to the end of the program and S_1 will not necessarily be followed by S_2 , i.e. there is an execution path from S_1 to the end of the program that does not go through S_2 . Expressed with the help of (post-)dominance the two conditions are equivalent to S_2 post-dominates all S_i S_2 does not post-dominate S_1

Text derived from https://en.wikipedia.org/w/index.php?oldid=1266290141 under CC BY-SA 4.0; modifications have been made.