docs/control-flow-analysis.txt

   1                        How Control Flow Analysis works in MCS
   2
   3                                 Martin Baulig
   4                               (martin@gnome.org)
   5                                       2002
   6
   7 This document gives you a short overview how control flow analysis
   8 works in MCS.
   9
  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).
  16
  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.
  20
  21 * Simple branchings
  22
  23 As a first rule, a local variable is only initialized if it's
  24 initialized in all possible branches:
  25
  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);
  32
  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.
  37
  38 * Control may return from the current block
  39
  40 However, there's an exception to this rule: control may return from
  41 the current block before it reaches its end:
  42
  43     1    int a;
  44     2    if (something)
  45     3       a = 3;
  46     4    else
  47     5       return;
  48     6    Console.WriteLine (a);
  49
  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.
  53
  54 This means that we must change this simple rule to:
  55
  56      A local variable must be initialized in all possible branches
  57      which do not return.
  58
  59 * `out' parameters
  60
  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.
  65
  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;
  74
  75 * Return vs. Break
  76
  77 This is not so simple as it looks like, let's assume `b' is an `out'
  78 parameter:
  79
  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);
  89
  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.
  93
  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).
  99
 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.
 104
 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.
 108
 109 * Forward gotos
 110
 111 In the following example, the local `a' isn't initialized in line 5
 112 since the assignment in line 3 is never executed:
 113
 114     1    int a;
 115     2    goto World;
 116     3    a = 4;
 117     4  World:
 118     5    Console.WriteLine (a);
 119
 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.
 126
 127 * Exception blocks
 128
 129 Things get a bit more difficult in exception blocks.
 130
 131 There are a few rules in exception blocks:
 132
 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.
 136
 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.
 140
 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.
 149
 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.
 154
 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.
 158
 159 Internally, the code handles a return in a try or catch block like a
 160 forward goto to the finally block.
 161
 162
 163 Last updated August 5th, 2002
 164 Martin Baulig <martin@gnome.org>