Lazily nit mono_class_setup_supertypes correctly.
[mono-project.git] / mcs / docs / control-flow-analysis.txt
blob939c8bbba0c209f7512dc7e4df492fced684df4f
1                        How Control Flow Analysis works in MCS
2         
3                                 Martin Baulig
4                               (martin@gnome.org)
5                                       2002
7 This document gives you a short overview how control flow analysis
8 works in MCS.
10 Control Flow Analysis is used to ensure that local variables are not
11 accessed before they have been initialized and that all `out'
12 parameters have been assigned before control leaves the current
13 method.  To do this, the compiler keeps two bitvectors - one for the
14 locals and one for the out parameters (the latter one isn't needed if
15 a method doesn't have any `out' parameters).
17 Each time the compiler encounters a branching of the program's control
18 flow, these bitvectors are duplicated for each of the possible
19 branches and then merged after the branching.
21 * Simple branchings
23 As a first rule, a local variable is only initialized if it's
24 initialized in all possible branches:
26     1    int a;
27     2    if (something)
28     3       a = 3;
29     4    else
30     5       Console.WriteLine ("Hello World");
31     6    Console.WriteLine (a);
33 In this example there's one branching of control flow (lines 2-5)
34 which has two branches: the `if' block in line 3 and the `else' block
35 in line 5.  In line 6, the local `a' hasn't been initialized because
36 it is only initialized in the `if' case, but not in the `else' case.
38 * Control may return from the current block
40 However, there's an exception to this rule: control may return from
41 the current block before it reaches its end:
43     1    int a;
44     2    if (something)
45     3       a = 3;
46     4    else
47     5       return;
48     6    Console.WriteLine (a);
50 In this case, line 6 will only be reached in the `if' case, but not in
51 the `else' case - so for the local `a' to be initialized, the `else'
52 clause is of no importance.
54 This means that we must change this simple rule to:
56      A local variable must be initialized in all possible branches
57      which do not return.
59 * `out' parameters
61 As a simple rule, an `out' parameter must be assigned before control
62 leaves the current method.  If `a' is an `out' parameter in the
63 following example, it must have been initialized in line 5 and in line
64 8 because control may return to the caller in these lines.
66     1    if (something)
67     2       Console.WriteLine ("Hello World");
68     3    else {
69     4       a = 8;
70     5       return;
71     6    }
72     7    a = 9;
73     8    return;
75 * Return vs. Break
77 This is not so simple as it looks like, let's assume `b' is an `out'
78 parameter:
80     1    int a;
81     2    do {
82     3       if (something)
83     3          a = 3;
84     4       else
85     5          break;
86     6       b = a;
87     7    } while (some_condition);
88     8    Console.WriteLine (a);
90 Regarding the local `a', the assignment in line 6 is allowed, but the
91 output in line 8 is not.  However, control only leaves the current
92 block in line 5, but not the whole method.
94 That's why the control flow code distinguishes between `break' and
95 `return' statements - a `break' statement is any statement which makes
96 control leave the current block (break, continue, goto, return) and a
97 `return' statement is a statement which makes control leave the
98 current method (return).
100 There are two `FlowReturns' states in the FlowBranching class:
101 `Breaks' specifies whether control may leave the current block before
102 reaching its end and `Returns' specifies whether control may leave the
103 current method before reaching the end of the current block.
105 At the end of each flow branching which may return, but which does not
106 always throw an exception, the state of all `out' parameters is
107 checked and if one of them isn't initialized, an error is reported.
109 * Forward gotos
111 In the following example, the local `a' isn't initialized in line 5
112 since the assignment in line 3 is never executed:
114     1    int a;
115     2    goto World;
116     3    a = 4;
117     4  World:
118     5    Console.WriteLine (a);
120 Each time the compiler encounters a forward goto, it duplicates the
121 bitvector with the current state of the locals and `out' parameters
122 and passed it to LabeledStatement.AddUserVector() to tell the label
123 that may be reached with a forward goto from a code position with that
124 state.  When the label is reached, the state of all these jump origins
125 is merged with the current state - see UsageVector.MergeJumpOrigins.
127 * Exception blocks
129 Things get a bit more difficult in exception blocks.
131 There are a few rules in exception blocks:
133 * A local is considered as being initialized after an exception block
134   if it has been initialized in either the try block and all not
135   always returning catch blocks or in the finally block.
137 * If the try block always throws an exception and the local is
138   initialized in all not always returning catch blocks, then it will
139   be initialized after the exception block.
141 * The code after the exception block is only reached if either the
142   whole try block is executed or none of the catch blocks may ever
143   return.  Since an exception may occur at any time in a try block,
144   the compiler can't know whether the whole try block will be executed
145   or not - so it needs to look only at the catch blocks to find out
146   whether the exception block may return or not.  The rule here is
147   that an exception block may return unless it has at least one catch
148   block and none of the catch blocks may ever return.
150 * Since the finally block is always executed, it is fine for an
151   `out' parameter to be initialized there.  The same applies for
152   locals - if a local or an `out' parameter is initialized in a
153   finally block, then it's always initialized.
155 * If the try or a catch block may return, all `out' parameters which
156   aren't initialized in the finally block must have been initialized
157   before the potential return.
159 Internally, the code handles a return in a try or catch block like a
160 forward goto to the finally block.
163 Last updated August 5th, 2002
164 Martin Baulig <martin@gnome.org>