2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
7 // (C) 2001, 2002, 2003 Ximian, Inc.
12 using System.Collections;
13 using System.Reflection;
14 using System.Reflection.Emit;
15 using System.Diagnostics;
20 // A new instance of this class is created every time a new block is resolved
21 // and if there's branching in the block's control flow.
23 public abstract class FlowBranching
26 // The type of a FlowBranching.
28 public enum BranchingType : byte {
29 // Normal (conditional or toplevel) block.
49 // The type of one sibling of a branching.
51 public enum SiblingType : byte {
61 // This is used in the control flow analysis code to specify whether the
62 // current code block may return to its enclosing block before reaching
65 public enum FlowReturns : byte {
68 // It can never return.
71 // This means that the block contains a conditional return statement
75 // The code always returns, ie. there's an unconditional return / break
80 public sealed class Reachability
82 FlowReturns returns, breaks, throws, barrier, reachable;
84 public FlowReturns Returns {
85 get { return returns; }
87 public FlowReturns Breaks {
88 get { return breaks; }
90 public FlowReturns Throws {
91 get { return throws; }
93 public FlowReturns Barrier {
94 get { return barrier; }
96 public FlowReturns Reachable {
97 get { return reachable; }
100 public Reachability (FlowReturns returns, FlowReturns breaks,
101 FlowReturns throws, FlowReturns barrier)
103 this.returns = returns;
104 this.breaks = breaks;
105 this.throws = throws;
106 this.barrier = barrier;
111 public Reachability Clone ()
113 Reachability cloned = new Reachability (returns, breaks, throws, barrier);
114 cloned.reachable = reachable;
119 // Performs an `And' operation on the FlowReturns status
120 // (for instance, a block only returns Always if all its siblings
123 public static FlowReturns AndFlowReturns (FlowReturns a, FlowReturns b)
125 if (a == FlowReturns.Undefined)
129 case FlowReturns.Never:
130 if (b == FlowReturns.Never)
131 return FlowReturns.Never;
133 return FlowReturns.Sometimes;
135 case FlowReturns.Sometimes:
136 return FlowReturns.Sometimes;
138 case FlowReturns.Always:
139 if (b == FlowReturns.Always)
140 return FlowReturns.Always;
142 return FlowReturns.Sometimes;
145 throw new ArgumentException ();
149 public static FlowReturns OrFlowReturns (FlowReturns a, FlowReturns b)
151 if (a == FlowReturns.Undefined)
155 case FlowReturns.Never:
158 case FlowReturns.Sometimes:
159 if (b == FlowReturns.Always)
160 return FlowReturns.Always;
162 return FlowReturns.Sometimes;
164 case FlowReturns.Always:
165 return FlowReturns.Always;
168 throw new ArgumentException ();
172 public static void And (ref Reachability a, Reachability b, bool do_break)
180 // `break' does not "break" in a Switch or a LoopBlock
182 bool a_breaks = do_break && a.AlwaysBreaks;
183 bool b_breaks = do_break && b.AlwaysBreaks;
185 bool a_has_barrier, b_has_barrier;
188 // This is the normal case: the code following a barrier
189 // cannot be reached.
191 a_has_barrier = a.AlwaysHasBarrier;
192 b_has_barrier = b.AlwaysHasBarrier;
195 // Special case for Switch and LoopBlocks: we can reach the
196 // code after the barrier via the `break'.
198 a_has_barrier = !a.AlwaysBreaks && a.AlwaysHasBarrier;
199 b_has_barrier = !b.AlwaysBreaks && b.AlwaysHasBarrier;
202 bool a_unreachable = a_breaks || a.AlwaysThrows || a_has_barrier;
203 bool b_unreachable = b_breaks || b.AlwaysThrows || b_has_barrier;
206 // Do all code paths always return ?
208 if (a.AlwaysReturns) {
209 if (b.AlwaysReturns || b_unreachable)
210 a.returns = FlowReturns.Always;
212 a.returns = FlowReturns.Sometimes;
213 } else if (b.AlwaysReturns) {
214 if (a.AlwaysReturns || a_unreachable)
215 a.returns = FlowReturns.Always;
217 a.returns = FlowReturns.Sometimes;
218 } else if (!a.MayReturn) {
220 a.returns = FlowReturns.Sometimes;
222 a.returns = FlowReturns.Never;
223 } else if (!b.MayReturn) {
225 a.returns = FlowReturns.Sometimes;
227 a.returns = FlowReturns.Never;
230 a.breaks = AndFlowReturns (a.breaks, b.breaks);
231 a.throws = AndFlowReturns (a.throws, b.throws);
232 a.barrier = AndFlowReturns (a.barrier, b.barrier);
234 a.reachable = AndFlowReturns (a.reachable, b.reachable);
237 public void Or (Reachability b)
239 returns = OrFlowReturns (returns, b.returns);
240 breaks = OrFlowReturns (breaks, b.breaks);
241 throws = OrFlowReturns (throws, b.throws);
242 barrier = OrFlowReturns (barrier, b.barrier);
247 public static Reachability Never ()
249 return new Reachability (
250 FlowReturns.Never, FlowReturns.Never,
251 FlowReturns.Never, FlowReturns.Never);
256 if ((returns == FlowReturns.Always) || (breaks == FlowReturns.Always) ||
257 (throws == FlowReturns.Always) || (barrier == FlowReturns.Always))
258 reachable = FlowReturns.Never;
259 else if ((returns == FlowReturns.Never) && (breaks == FlowReturns.Never) &&
260 (throws == FlowReturns.Never) && (barrier == FlowReturns.Never))
261 reachable = FlowReturns.Always;
263 reachable = FlowReturns.Sometimes;
266 public bool AlwaysBreaks {
267 get { return breaks == FlowReturns.Always; }
270 public bool MayBreak {
271 get { return breaks != FlowReturns.Never; }
274 public bool AlwaysReturns {
275 get { return returns == FlowReturns.Always; }
278 public bool MayReturn {
279 get { return returns != FlowReturns.Never; }
282 public bool AlwaysThrows {
283 get { return throws == FlowReturns.Always; }
286 public bool MayThrow {
287 get { return throws != FlowReturns.Never; }
290 public bool AlwaysHasBarrier {
291 get { return barrier == FlowReturns.Always; }
294 public bool MayHaveBarrier {
295 get { return barrier != FlowReturns.Never; }
298 public bool IsUnreachable {
299 get { return reachable == FlowReturns.Never; }
302 public void SetReturns ()
304 returns = FlowReturns.Always;
308 public void SetReturnsSometimes ()
310 returns = FlowReturns.Sometimes;
314 public void SetBreaks ()
316 breaks = FlowReturns.Always;
320 public void ResetBreaks ()
322 breaks = FlowReturns.Never;
326 public void SetThrows ()
328 throws = FlowReturns.Always;
332 public void SetThrowsSometimes ()
334 throws = FlowReturns.Sometimes;
338 public void SetBarrier ()
340 barrier = FlowReturns.Always;
344 static string ShortName (FlowReturns returns)
347 case FlowReturns.Never:
349 case FlowReturns.Sometimes:
356 public override string ToString ()
358 return String.Format ("[{0}:{1}:{2}:{3}:{4}]",
359 ShortName (returns), ShortName (breaks),
360 ShortName (throws), ShortName (barrier),
361 ShortName (reachable));
365 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
368 case BranchingType.Exception:
369 return new FlowBranchingException (parent, block, loc);
371 case BranchingType.Switch:
372 return new FlowBranchingBlock (parent, type, SiblingType.SwitchSection, block, loc);
374 case BranchingType.SwitchSection:
375 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
377 case BranchingType.Block:
378 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
380 case BranchingType.Loop:
381 return new FlowBranchingLoop (parent, block, loc);
384 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
389 // The type of this flow branching.
391 public readonly BranchingType Type;
394 // The block this branching is contained in. This may be null if it's not
395 // a top-level block and it doesn't declare any local variables.
397 public readonly Block Block;
400 // The parent of this branching or null if this is the top-block.
402 public readonly FlowBranching Parent;
405 // Start-Location of this flow branching.
407 public readonly Location Location;
410 // If this is an infinite loop.
412 public bool Infinite;
417 VariableMap param_map, local_map;
419 static int next_id = 0;
423 // The vector contains a BitArray with information about which local variables
424 // and parameters are already initialized at the current code position.
426 public class UsageVector {
428 // The type of this branching.
430 public readonly SiblingType Type;
433 // Start location of this branching.
435 public readonly Location Location;
438 // This is only valid for SwitchSection, Try, Catch and Finally.
440 public readonly Block Block;
443 // If this is true, then the usage vector has been modified and must be
444 // merged when we're done with this branching.
449 // The number of parameters in this block.
451 public readonly int CountParameters;
454 // The number of locals in this block.
456 public readonly int CountLocals;
459 // If not null, then we inherit our state from this vector and do a
460 // copy-on-write. If null, then we're the first sibling in a top-level
461 // block and inherit from the empty vector.
463 public readonly UsageVector InheritsFrom;
466 // This is used to construct a list of UsageVector's.
468 public UsageVector Next;
473 MyBitVector locals, parameters;
474 Reachability reachability;
476 static int next_id = 0;
480 // Normally, you should not use any of these constructors.
482 public UsageVector (SiblingType type, UsageVector parent,
483 Block block, Location loc,
484 int num_params, int num_locals)
489 this.InheritsFrom = parent;
490 this.CountParameters = num_params;
491 this.CountLocals = num_locals;
493 if (parent != null) {
495 locals = new MyBitVector (parent.locals, CountLocals);
498 parameters = new MyBitVector (parent.parameters, num_params);
500 reachability = parent.Reachability.Clone ();
503 locals = new MyBitVector (null, CountLocals);
506 parameters = new MyBitVector (null, num_params);
508 reachability = Reachability.Never ();
514 public UsageVector (SiblingType type, UsageVector parent,
515 Block block, Location loc)
516 : this (type, parent, block, loc,
517 parent.CountParameters, parent.CountLocals)
520 public UsageVector (MyBitVector parameters, MyBitVector locals,
521 Reachability reachability, Block block,
524 this.Type = SiblingType.Block;
528 this.reachability = reachability;
529 this.parameters = parameters;
530 this.locals = locals;
536 // This does a deep copy of the usage vector.
538 public UsageVector Clone ()
540 UsageVector retval = new UsageVector (
541 Type, null, Block, Location,
542 CountParameters, CountLocals);
544 if (retval.locals != null)
545 retval.locals = locals.Clone ();
547 if (parameters != null)
548 retval.parameters = parameters.Clone ();
550 retval.reachability = reachability.Clone ();
555 public bool IsAssigned (VariableInfo var)
557 if (!var.IsParameter && Reachability.IsUnreachable)
560 return var.IsAssigned (var.IsParameter ? parameters : locals);
563 public void SetAssigned (VariableInfo var)
565 if (!var.IsParameter && Reachability.IsUnreachable)
569 var.SetAssigned (var.IsParameter ? parameters : locals);
572 public bool IsFieldAssigned (VariableInfo var, string name)
574 if (!var.IsParameter && Reachability.IsUnreachable)
577 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
580 public void SetFieldAssigned (VariableInfo var, string name)
582 if (!var.IsParameter && Reachability.IsUnreachable)
586 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
589 public Reachability Reachability {
595 public void Return ()
597 if (!reachability.IsUnreachable) {
599 reachability.SetReturns ();
605 if (!reachability.IsUnreachable) {
607 reachability.SetBreaks ();
613 if (!reachability.IsUnreachable) {
615 reachability.SetThrows ();
621 if (!reachability.IsUnreachable) {
623 reachability.SetBarrier ();
628 // Merges a child branching.
630 public UsageVector MergeChild (FlowBranching branching)
632 UsageVector result = branching.Merge ();
634 Report.Debug (2, " MERGING CHILD", this, IsDirty,
635 result.ParameterVector, result.LocalVector,
636 result.Reachability, reachability, Type);
638 Reachability new_r = result.Reachability;
640 if (branching.Type == BranchingType.Loop) {
641 bool may_leave_loop = new_r.MayBreak;
642 new_r.ResetBreaks ();
644 if (branching.Infinite && !may_leave_loop) {
645 if (new_r.Returns == FlowReturns.Sometimes) {
646 // If we're an infinite loop and do not break,
647 // the code after the loop can never be reached.
648 // However, if we may return from the loop,
649 // then we do always return (or stay in the
656 if (new_r.Returns == FlowReturns.Always) {
657 // We're either finite or we may leave the loop.
658 new_r.SetReturnsSometimes ();
660 if (new_r.Throws == FlowReturns.Always) {
661 // We're either finite or we may leave the loop.
662 new_r.SetThrowsSometimes ();
665 } else if (branching.Type == BranchingType.Switch)
666 new_r.ResetBreaks ();
669 // We've now either reached the point after the branching or we will
670 // never get there since we always return or always throw an exception.
672 // If we can reach the point after the branching, mark all locals and
673 // parameters as initialized which have been initialized in all branches
674 // we need to look at (see above).
677 if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
678 Report.Error (163, Location,
679 "Control cannot fall through from one " +
680 "case label to another");
684 if (locals != null && result.LocalVector != null)
685 locals.Or (result.LocalVector);
687 if (result.ParameterVector != null)
688 parameters.Or (result.ParameterVector);
690 reachability.Or (new_r);
692 Report.Debug (2, " MERGING CHILD DONE", this, result,
693 new_r, reachability);
700 protected void MergeFinally (FlowBranching branching, UsageVector f_origins,
701 MyBitVector f_params)
703 for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
704 MyBitVector temp_params = f_params.Clone ();
705 temp_params.Or (vector.Parameters);
709 public void MergeFinally (FlowBranching branching, UsageVector f_vector,
710 UsageVector f_origins)
712 if (parameters != null) {
713 if (f_vector != null) {
714 MergeFinally (branching, f_origins, f_vector.Parameters);
715 MyBitVector.Or (ref parameters, f_vector.ParameterVector);
717 MergeFinally (branching, f_origins, parameters);
720 if (f_vector != null && f_vector.LocalVector != null)
721 MyBitVector.Or (ref locals, f_vector.LocalVector);
725 // Tells control flow analysis that the current code position may be reached with
726 // a forward jump from any of the origins listed in `origin_vectors' which is a
727 // list of UsageVectors.
729 // This is used when resolving forward gotos - in the following example, the
730 // variable `a' is uninitialized in line 8 becase this line may be reached via
731 // the goto in line 4:
741 // 8 Console.WriteLine (a);
744 public void MergeJumpOrigins (UsageVector o_vectors)
746 Report.Debug (1, " MERGING JUMP ORIGINS", this);
748 reachability = Reachability.Never ();
750 if (o_vectors == null)
755 for (UsageVector vector = o_vectors; vector != null;
756 vector = vector.Next) {
757 Report.Debug (1, " MERGING JUMP ORIGIN", vector);
760 if (locals != null && vector.Locals != null)
761 locals.Or (vector.locals);
763 if (parameters != null)
764 parameters.Or (vector.parameters);
767 if (locals != null && vector.Locals != null)
768 locals.And (vector.locals);
769 if (parameters != null)
770 parameters.And (vector.parameters);
773 Reachability.And (ref reachability, vector.Reachability, true);
776 Report.Debug (1, " MERGING JUMP ORIGINS DONE", this);
780 // This is used at the beginning of a finally block if there were
781 // any return statements in the try block or one of the catch blocks.
783 public void MergeFinallyOrigins (UsageVector f_origins)
785 Report.Debug (1, " MERGING FINALLY ORIGIN", this);
787 reachability = Reachability.Never ();
789 for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
790 Report.Debug (1, " MERGING FINALLY ORIGIN", vector);
792 if (parameters != null)
793 parameters.And (vector.parameters);
795 Reachability.And (ref reachability, vector.Reachability, true);
798 Report.Debug (1, " MERGING FINALLY ORIGIN DONE", this);
801 public void MergeBreakOrigins (UsageVector o_vectors)
803 Report.Debug (1, " MERGING BREAK ORIGINS", this);
805 if (o_vectors == null)
810 for (UsageVector vector = o_vectors; vector != null;
811 vector = vector.Next) {
812 Report.Debug (1, " MERGING BREAK ORIGIN", vector);
815 if (locals != null && vector.Locals != null)
816 locals.Or (vector.locals);
818 if (parameters != null)
819 parameters.Or (vector.parameters);
822 if (locals != null && vector.Locals != null)
823 locals.And (vector.locals);
824 if (parameters != null)
825 parameters.And (vector.parameters);
829 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
832 public void CheckOutParameters (FlowBranching branching)
834 if (parameters != null)
835 branching.CheckOutParameters (parameters, branching.Location);
839 // Performs an `or' operation on the locals and the parameters.
841 public void Or (UsageVector new_vector)
844 locals.Or (new_vector.locals);
845 if (parameters != null)
846 parameters.Or (new_vector.parameters);
850 // Performs an `and' operation on the locals.
852 public void AndLocals (UsageVector new_vector)
855 locals.And (new_vector.locals);
858 public bool HasParameters {
860 return parameters != null;
864 public bool HasLocals {
866 return locals != null;
871 // Returns a deep copy of the parameters.
873 public MyBitVector Parameters {
875 if (parameters != null)
876 return parameters.Clone ();
883 // Returns a deep copy of the locals.
885 public MyBitVector Locals {
888 return locals.Clone ();
894 public MyBitVector ParameterVector {
900 public MyBitVector LocalVector {
910 public override string ToString ()
912 StringBuilder sb = new StringBuilder ();
914 sb.Append ("Vector (");
921 sb.Append (reachability);
922 if (parameters != null) {
924 sb.Append (parameters);
930 return sb.ToString ();
935 // Creates a new flow branching which is contained in `parent'.
936 // You should only pass non-null for the `block' argument if this block
937 // introduces any new variables - in this case, we need to create a new
938 // usage vector with a different size than our parent's one.
940 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
941 Block block, Location loc)
951 param_map = Block.ParameterMap;
952 local_map = Block.LocalMap;
954 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
955 vector = new UsageVector (
956 stype, parent_vector, Block, loc,
957 param_map.Length, local_map.Length);
959 param_map = Parent.param_map;
960 local_map = Parent.local_map;
961 vector = new UsageVector (
962 stype, Parent.CurrentUsageVector, null, loc);
968 public abstract UsageVector CurrentUsageVector {
973 // Creates a sibling of the current usage vector.
975 public virtual void CreateSibling (Block block, SiblingType type)
977 UsageVector vector = new UsageVector (
978 type, Parent.CurrentUsageVector, block, Location);
981 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
984 public void CreateSibling ()
986 CreateSibling (null, SiblingType.Conditional);
989 protected abstract void AddSibling (UsageVector uv);
991 public virtual LabeledStatement LookupLabel (string name, Location loc)
994 return Parent.LookupLabel (name, loc);
998 "No such label `" + name + "' in this scope");
1002 public abstract void Label (UsageVector origin_vectors);
1005 // Check whether all `out' parameters have been assigned.
1007 public void CheckOutParameters (MyBitVector parameters, Location loc)
1009 for (int i = 0; i < param_map.Count; i++) {
1010 VariableInfo var = param_map [i];
1015 if (var.IsAssigned (parameters))
1018 Report.Error (177, loc, "The out parameter `" +
1019 var.Name + "' must be " +
1020 "assigned before control leave the current method.");
1024 protected UsageVector Merge (UsageVector sibling_list)
1026 if (sibling_list.Next == null)
1027 return sibling_list;
1029 MyBitVector locals = null;
1030 MyBitVector parameters = null;
1032 Reachability reachability = null;
1034 Report.Debug (2, " MERGING SIBLINGS", this, Name);
1036 for (UsageVector child = sibling_list; child != null; child = child.Next) {
1037 bool do_break = (Type != BranchingType.Switch) &&
1038 (Type != BranchingType.Loop);
1040 Report.Debug (2, " MERGING SIBLING ", child,
1041 child.ParameterVector, child.LocalVector,
1042 reachability, child.Reachability, do_break);
1044 Reachability.And (ref reachability, child.Reachability, do_break);
1046 // A local variable is initialized after a flow branching if it
1047 // has been initialized in all its branches which do neither
1048 // always return or always throw an exception.
1050 // If a branch may return, but does not always return, then we
1051 // can treat it like a never-returning branch here: control will
1052 // only reach the code position after the branching if we did not
1055 // It's important to distinguish between always and sometimes
1056 // returning branches here:
1059 // 2 if (something) {
1063 // 6 Console.WriteLine (a);
1065 // The if block in lines 3-4 always returns, so we must not look
1066 // at the initialization of `a' in line 4 - thus it'll still be
1067 // uninitialized in line 6.
1069 // On the other hand, the following is allowed:
1076 // 6 Console.WriteLine (a);
1078 // Here, `a' is initialized in line 3 and we must not look at
1079 // line 5 since it always returns.
1081 bool do_break_2 = (child.Type != SiblingType.Block) &&
1082 (child.Type != SiblingType.SwitchSection);
1083 bool always_throws = (child.Type != SiblingType.Try) &&
1084 child.Reachability.AlwaysThrows;
1085 bool unreachable = always_throws ||
1086 (do_break_2 && child.Reachability.AlwaysBreaks) ||
1087 child.Reachability.AlwaysReturns ||
1088 child.Reachability.AlwaysHasBarrier;
1090 Report.Debug (2, " MERGING SIBLING #1", reachability,
1091 Type, child.Type, child.Reachability.IsUnreachable,
1092 do_break_2, always_throws, unreachable);
1094 if (!unreachable && (child.LocalVector != null))
1095 MyBitVector.And (ref locals, child.LocalVector);
1097 // An `out' parameter must be assigned in all branches which do
1098 // not always throw an exception.
1099 if ((child.ParameterVector != null) && !child.Reachability.AlwaysThrows)
1100 MyBitVector.And (ref parameters, child.ParameterVector);
1102 Report.Debug (2, " MERGING SIBLING #2", parameters, locals);
1105 if (reachability == null)
1106 reachability = Reachability.Never ();
1108 Report.Debug (2, " MERGING SIBLINGS DONE", parameters, locals,
1109 reachability, Infinite);
1111 return new UsageVector (
1112 parameters, locals, reachability, null, Location);
1115 protected abstract UsageVector Merge ();
1118 // Merge a child branching.
1120 public UsageVector MergeChild (FlowBranching child)
1122 return CurrentUsageVector.MergeChild (child);
1126 // Does the toplevel merging.
1128 public Reachability MergeTopBlock ()
1130 if ((Type != BranchingType.Block) || (Block == null))
1131 throw new NotSupportedException ();
1133 UsageVector vector = new UsageVector (
1134 SiblingType.Conditional, null, Block, Location,
1135 param_map.Length, local_map.Length);
1137 UsageVector result = vector.MergeChild (this);
1139 Report.Debug (4, "MERGE TOP BLOCK", Location, vector, result.Reachability);
1141 if (vector.Reachability.Throws != FlowReturns.Always)
1142 CheckOutParameters (vector.Parameters, Location);
1144 return result.Reachability;
1148 // Checks whether we're in a `try' block.
1150 public virtual bool InTryOrCatch (bool is_return)
1152 if ((Block != null) && Block.IsDestructor)
1154 else if (!is_return &&
1155 ((Type == BranchingType.Loop) || (Type == BranchingType.Switch)))
1157 else if (Parent != null)
1158 return Parent.InTryOrCatch (is_return);
1164 // Checks whether we're in a `catch' block.
1166 public virtual bool InCatch ()
1169 return Parent.InCatch ();
1175 // Checks whether we're in a `finally' block.
1177 public virtual bool InFinally (bool is_return)
1180 ((Type == BranchingType.Loop) || (Type == BranchingType.Switch)))
1182 else if (Parent != null)
1183 return Parent.InFinally (is_return);
1188 public virtual bool InLoop ()
1190 if (Type == BranchingType.Loop)
1192 else if (Parent != null)
1193 return Parent.InLoop ();
1198 public virtual bool InSwitch ()
1200 if (Type == BranchingType.Switch)
1202 else if (Parent != null)
1203 return Parent.InSwitch ();
1208 public virtual bool BreakCrossesTryCatchBoundary ()
1210 if ((Type == BranchingType.Loop) || (Type == BranchingType.Switch))
1212 else if (Parent != null)
1213 return Parent.BreakCrossesTryCatchBoundary ();
1218 public virtual void AddFinallyVector (UsageVector vector)
1221 Parent.AddFinallyVector (vector);
1222 else if ((Block == null) || !Block.IsDestructor)
1223 throw new NotSupportedException ();
1226 public virtual void AddBreakVector (UsageVector vector)
1229 Parent.AddBreakVector (vector);
1230 else if ((Block == null) || !Block.IsDestructor)
1231 throw new NotSupportedException ();
1234 public bool IsAssigned (VariableInfo vi)
1236 return CurrentUsageVector.IsAssigned (vi);
1239 public bool IsFieldAssigned (VariableInfo vi, string field_name)
1241 if (CurrentUsageVector.IsAssigned (vi))
1244 return CurrentUsageVector.IsFieldAssigned (vi, field_name);
1247 public void SetAssigned (VariableInfo vi)
1249 CurrentUsageVector.SetAssigned (vi);
1252 public void SetFieldAssigned (VariableInfo vi, string name)
1254 CurrentUsageVector.SetFieldAssigned (vi, name);
1257 public override string ToString ()
1259 StringBuilder sb = new StringBuilder ();
1260 sb.Append (GetType ());
1266 if (Block != null) {
1268 sb.Append (Block.ID);
1270 sb.Append (Block.StartLocation);
1273 // sb.Append (Siblings.Length);
1274 // sb.Append (" - ");
1275 sb.Append (CurrentUsageVector);
1277 return sb.ToString ();
1280 public string Name {
1282 return String.Format ("{0} ({1}:{2}:{3})",
1283 GetType (), id, Type, Location);
1288 public class FlowBranchingBlock : FlowBranching
1290 UsageVector sibling_list = null;
1292 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
1293 SiblingType stype, Block block, Location loc)
1294 : base (parent, type, stype, block, loc)
1297 public override UsageVector CurrentUsageVector {
1298 get { return sibling_list; }
1301 protected override void AddSibling (UsageVector sibling)
1303 sibling.Next = sibling_list;
1304 sibling_list = sibling;
1307 public override LabeledStatement LookupLabel (string name, Location loc)
1310 return base.LookupLabel (name, loc);
1312 LabeledStatement s = Block.LookupLabel (name);
1316 return base.LookupLabel (name, loc);
1319 public override void Label (UsageVector origin_vectors)
1321 if (!CurrentUsageVector.Reachability.IsUnreachable) {
1322 UsageVector vector = CurrentUsageVector.Clone ();
1323 vector.Next = origin_vectors;
1324 origin_vectors = vector;
1327 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1330 protected override UsageVector Merge ()
1332 return Merge (sibling_list);
1336 public class FlowBranchingLoop : FlowBranchingBlock
1338 UsageVector break_origins;
1340 public FlowBranchingLoop (FlowBranching parent, Block block, Location loc)
1341 : base (parent, BranchingType.Loop, SiblingType.Conditional, block, loc)
1344 public override void AddBreakVector (UsageVector vector)
1346 vector = vector.Clone ();
1347 vector.Next = break_origins;
1348 break_origins = vector;
1351 protected override UsageVector Merge ()
1353 UsageVector vector = base.Merge ();
1355 vector.MergeBreakOrigins (break_origins);
1361 public class FlowBranchingException : FlowBranching
1363 UsageVector current_vector;
1364 UsageVector catch_vectors;
1365 UsageVector finally_vector;
1366 UsageVector finally_origins;
1369 public FlowBranchingException (FlowBranching parent, Block block, Location loc)
1370 : base (parent, BranchingType.Exception, SiblingType.Try, block, loc)
1373 protected override void AddSibling (UsageVector sibling)
1375 if (sibling.Type == SiblingType.Try) {
1376 sibling.Next = catch_vectors;
1377 catch_vectors = sibling;
1379 } else if (sibling.Type == SiblingType.Catch) {
1380 sibling.Next = catch_vectors;
1381 catch_vectors = sibling;
1383 } else if (sibling.Type == SiblingType.Finally) {
1384 sibling.MergeFinallyOrigins (finally_origins);
1385 finally_vector = sibling;
1388 throw new InvalidOperationException ();
1390 current_vector = sibling;
1393 public override UsageVector CurrentUsageVector {
1394 get { return current_vector; }
1397 public override bool InTryOrCatch (bool is_return)
1399 return finally_vector == null;
1402 public override bool InCatch ()
1404 return !in_try && (finally_vector == null);
1407 public override bool InFinally (bool is_return)
1409 return finally_vector != null;
1412 public override bool BreakCrossesTryCatchBoundary ()
1417 public override void AddFinallyVector (UsageVector vector)
1419 vector = vector.Clone ();
1420 vector.Next = finally_origins;
1421 finally_origins = vector;
1424 public override LabeledStatement LookupLabel (string name, Location loc)
1426 LabeledStatement s = current_vector.Block.LookupLabel (name);
1430 if (finally_vector != null) {
1432 157, loc, "Control can not leave the body " +
1433 "of the finally block");
1437 return base.LookupLabel (name, loc);
1440 public override void Label (UsageVector origin_vectors)
1442 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1445 protected override UsageVector Merge ()
1447 UsageVector vector = Merge (catch_vectors);
1449 vector.MergeFinally (this, finally_vector, finally_origins);
1456 // This is used by the flow analysis code to keep track of the type of local variables
1459 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1460 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1461 // you can only assign the whole variable as such.
1463 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1464 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1465 // one bit for each of its fields.
1467 // This class computes this `layout' for each type.
1469 public class TypeInfo
1471 public readonly Type Type;
1474 // Total number of bits a variable of this type consumes in the flow vector.
1476 public readonly int TotalLength;
1479 // Number of bits the simple fields of a variable of this type consume
1480 // in the flow vector.
1482 public readonly int Length;
1485 // This is only used by sub-structs.
1487 public readonly int Offset;
1490 // If this is a struct.
1492 public readonly bool IsStruct;
1495 // If this is a struct, all fields which are structs theirselves.
1497 public TypeInfo[] SubStructInfo;
1499 protected readonly StructInfo struct_info;
1500 private static Hashtable type_hash = new Hashtable ();
1502 public static TypeInfo GetTypeInfo (Type type)
1504 TypeInfo info = (TypeInfo) type_hash [type];
1508 info = new TypeInfo (type);
1509 type_hash.Add (type, info);
1513 public static TypeInfo GetTypeInfo (TypeContainer tc)
1515 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1519 info = new TypeInfo (tc);
1520 type_hash.Add (tc.TypeBuilder, info);
1524 private TypeInfo (Type type)
1528 struct_info = StructInfo.GetStructInfo (type);
1529 if (struct_info != null) {
1530 Length = struct_info.Length;
1531 TotalLength = struct_info.TotalLength;
1532 SubStructInfo = struct_info.StructFields;
1541 private TypeInfo (TypeContainer tc)
1543 this.Type = tc.TypeBuilder;
1545 struct_info = StructInfo.GetStructInfo (tc);
1546 if (struct_info != null) {
1547 Length = struct_info.Length;
1548 TotalLength = struct_info.TotalLength;
1549 SubStructInfo = struct_info.StructFields;
1558 protected TypeInfo (StructInfo struct_info, int offset)
1560 this.struct_info = struct_info;
1561 this.Offset = offset;
1562 this.Length = struct_info.Length;
1563 this.TotalLength = struct_info.TotalLength;
1564 this.SubStructInfo = struct_info.StructFields;
1565 this.Type = struct_info.Type;
1566 this.IsStruct = true;
1569 public int GetFieldIndex (string name)
1571 if (struct_info == null)
1574 return struct_info [name];
1577 public TypeInfo GetSubStruct (string name)
1579 if (struct_info == null)
1582 return struct_info.GetStructField (name);
1586 // A struct's constructor must always assign all fields.
1587 // This method checks whether it actually does so.
1589 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1591 if (struct_info == null)
1595 for (int i = 0; i < struct_info.Count; i++) {
1596 FieldInfo field = struct_info.Fields [i];
1598 if (!branching.IsFieldAssigned (vi, field.Name)) {
1599 Report.Error (171, loc,
1600 "Field `" + TypeManager.CSharpName (Type) +
1601 "." + field.Name + "' must be fully initialized " +
1602 "before control leaves the constructor");
1610 public override string ToString ()
1612 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1613 Type, Offset, Length, TotalLength);
1616 protected class StructInfo {
1617 public readonly Type Type;
1618 public readonly FieldInfo[] Fields;
1619 public readonly TypeInfo[] StructFields;
1620 public readonly int Count;
1621 public readonly int CountPublic;
1622 public readonly int CountNonPublic;
1623 public readonly int Length;
1624 public readonly int TotalLength;
1625 public readonly bool HasStructFields;
1627 private static Hashtable field_type_hash = new Hashtable ();
1628 private Hashtable struct_field_hash;
1629 private Hashtable field_hash;
1631 protected bool InTransit = false;
1633 // Private constructor. To save memory usage, we only need to create one instance
1634 // of this class per struct type.
1635 private StructInfo (Type type)
1639 field_type_hash.Add (type, this);
1641 if (type is TypeBuilder) {
1642 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1644 ArrayList fields = tc.Fields;
1646 ArrayList public_fields = new ArrayList ();
1647 ArrayList non_public_fields = new ArrayList ();
1649 if (fields != null) {
1650 foreach (Field field in fields) {
1651 if ((field.ModFlags & Modifiers.STATIC) != 0)
1653 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1654 public_fields.Add (field.FieldBuilder);
1656 non_public_fields.Add (field.FieldBuilder);
1660 CountPublic = public_fields.Count;
1661 CountNonPublic = non_public_fields.Count;
1662 Count = CountPublic + CountNonPublic;
1664 Fields = new FieldInfo [Count];
1665 public_fields.CopyTo (Fields, 0);
1666 non_public_fields.CopyTo (Fields, CountPublic);
1668 FieldInfo[] public_fields = type.GetFields (
1669 BindingFlags.Instance|BindingFlags.Public);
1670 FieldInfo[] non_public_fields = type.GetFields (
1671 BindingFlags.Instance|BindingFlags.NonPublic);
1673 CountPublic = public_fields.Length;
1674 CountNonPublic = non_public_fields.Length;
1675 Count = CountPublic + CountNonPublic;
1677 Fields = new FieldInfo [Count];
1678 public_fields.CopyTo (Fields, 0);
1679 non_public_fields.CopyTo (Fields, CountPublic);
1682 struct_field_hash = new Hashtable ();
1683 field_hash = new Hashtable ();
1686 StructFields = new TypeInfo [Count];
1687 StructInfo[] sinfo = new StructInfo [Count];
1691 for (int i = 0; i < Count; i++) {
1692 FieldInfo field = (FieldInfo) Fields [i];
1694 sinfo [i] = GetStructInfo (field.FieldType);
1695 if (sinfo [i] == null)
1696 field_hash.Add (field.Name, ++Length);
1697 else if (sinfo [i].InTransit) {
1698 Report.Error (523, String.Format (
1699 "Struct member '{0}.{1}' of type '{2}' causes " +
1700 "a cycle in the structure layout",
1701 type, field.Name, sinfo [i].Type));
1709 TotalLength = Length + 1;
1710 for (int i = 0; i < Count; i++) {
1711 FieldInfo field = (FieldInfo) Fields [i];
1713 if (sinfo [i] == null)
1716 field_hash.Add (field.Name, TotalLength);
1718 HasStructFields = true;
1719 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1720 struct_field_hash.Add (field.Name, StructFields [i]);
1721 TotalLength += sinfo [i].TotalLength;
1725 public int this [string name] {
1727 if (field_hash.Contains (name))
1728 return (int) field_hash [name];
1734 public TypeInfo GetStructField (string name)
1736 return (TypeInfo) struct_field_hash [name];
1739 public static StructInfo GetStructInfo (Type type)
1741 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1742 TypeManager.IsBuiltinType (type))
1745 StructInfo info = (StructInfo) field_type_hash [type];
1749 return new StructInfo (type);
1752 public static StructInfo GetStructInfo (TypeContainer tc)
1754 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1758 return new StructInfo (tc.TypeBuilder);
1764 // This is used by the flow analysis code to store information about a single local variable
1765 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1766 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1767 // it has been assigned or not, but for structs, we need this information for each of its fields.
1769 public class VariableInfo {
1770 public readonly string Name;
1771 public readonly TypeInfo TypeInfo;
1774 // The bit offset of this variable in the flow vector.
1776 public readonly int Offset;
1779 // The number of bits this variable needs in the flow vector.
1780 // The first bit always specifies whether the variable as such has been assigned while
1781 // the remaining bits contain this information for each of a struct's fields.
1783 public readonly int Length;
1786 // If this is a parameter of local variable.
1788 public readonly bool IsParameter;
1790 public readonly LocalInfo LocalInfo;
1791 public readonly int ParameterIndex;
1793 readonly VariableInfo Parent;
1794 VariableInfo[] sub_info;
1796 protected VariableInfo (string name, Type type, int offset)
1799 this.Offset = offset;
1800 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1802 Length = TypeInfo.TotalLength;
1807 protected VariableInfo (VariableInfo parent, TypeInfo type)
1809 this.Name = parent.Name;
1810 this.TypeInfo = type;
1811 this.Offset = parent.Offset + type.Offset;
1812 this.Parent = parent;
1813 this.Length = type.TotalLength;
1815 this.IsParameter = parent.IsParameter;
1816 this.LocalInfo = parent.LocalInfo;
1817 this.ParameterIndex = parent.ParameterIndex;
1822 protected void Initialize ()
1824 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1825 if (sub_fields != null) {
1826 sub_info = new VariableInfo [sub_fields.Length];
1827 for (int i = 0; i < sub_fields.Length; i++) {
1828 if (sub_fields [i] != null)
1829 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1832 sub_info = new VariableInfo [0];
1835 public VariableInfo (LocalInfo local_info, int offset)
1836 : this (local_info.Name, local_info.VariableType, offset)
1838 this.LocalInfo = local_info;
1839 this.IsParameter = false;
1842 public VariableInfo (string name, Type type, int param_idx, int offset)
1843 : this (name, type, offset)
1845 this.ParameterIndex = param_idx;
1846 this.IsParameter = true;
1849 public bool IsAssigned (EmitContext ec)
1851 return !ec.DoFlowAnalysis || ec.CurrentBranching.IsAssigned (this);
1854 public bool IsAssigned (EmitContext ec, Location loc)
1856 if (IsAssigned (ec))
1859 Report.Error (165, loc,
1860 "Use of unassigned local variable `" + Name + "'");
1861 ec.CurrentBranching.SetAssigned (this);
1865 public bool IsAssigned (MyBitVector vector)
1867 if (vector [Offset])
1870 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1871 if (vector [parent.Offset])
1874 // Return unless this is a struct.
1875 if (!TypeInfo.IsStruct)
1878 // Ok, so each field must be assigned.
1879 for (int i = 0; i < TypeInfo.Length; i++) {
1880 if (!vector [Offset + i + 1])
1884 // Ok, now check all fields which are structs.
1885 for (int i = 0; i < sub_info.Length; i++) {
1886 VariableInfo sinfo = sub_info [i];
1890 if (!sinfo.IsAssigned (vector))
1894 vector [Offset] = true;
1898 public void SetAssigned (EmitContext ec)
1900 if (ec.DoFlowAnalysis)
1901 ec.CurrentBranching.SetAssigned (this);
1904 public void SetAssigned (MyBitVector vector)
1906 vector [Offset] = true;
1909 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1911 if (!ec.DoFlowAnalysis || ec.CurrentBranching.IsFieldAssigned (this, name))
1914 Report.Error (170, loc,
1915 "Use of possibly unassigned field `" + name + "'");
1916 ec.CurrentBranching.SetFieldAssigned (this, name);
1920 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1922 int field_idx = TypeInfo.GetFieldIndex (field_name);
1927 return vector [Offset + field_idx];
1930 public void SetFieldAssigned (EmitContext ec, string name)
1932 if (ec.DoFlowAnalysis)
1933 ec.CurrentBranching.SetFieldAssigned (this, name);
1936 public void SetFieldAssigned (MyBitVector vector, string field_name)
1938 int field_idx = TypeInfo.GetFieldIndex (field_name);
1943 vector [Offset + field_idx] = true;
1946 public VariableInfo GetSubStruct (string name)
1948 TypeInfo type = TypeInfo.GetSubStruct (name);
1953 return new VariableInfo (this, type);
1956 public override string ToString ()
1958 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1959 Name, TypeInfo, Offset, Length, IsParameter);
1964 // This is used by the flow code to hold the `layout' of the flow vector for
1965 // all locals and all parameters (ie. we create one instance of this class for the
1966 // locals and another one for the params).
1968 public class VariableMap {
1970 // The number of variables in the map.
1972 public readonly int Count;
1975 // Total length of the flow vector for this map.
1977 public readonly int Length;
1981 public VariableMap (InternalParameters ip)
1983 Count = ip != null ? ip.Count : 0;
1985 // Dont bother allocating anything!
1991 for (int i = 0; i < Count; i++) {
1992 Parameter.Modifier mod = ip.ParameterModifier (i);
1994 if ((mod & Parameter.Modifier.OUT) == 0)
1997 // Dont allocate till we find an out var.
1999 map = new VariableInfo [Count];
2001 map [i] = new VariableInfo (ip.ParameterName (i),
2002 TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
2004 Length += map [i].Length;
2008 public VariableMap (LocalInfo[] locals)
2009 : this (null, locals)
2012 public VariableMap (VariableMap parent, LocalInfo[] locals)
2014 int offset = 0, start = 0;
2015 if (parent != null && parent.map != null) {
2016 offset = parent.Length;
2017 start = parent.Count;
2020 Count = locals.Length + start;
2025 map = new VariableInfo [Count];
2028 if (parent != null && parent.map != null) {
2029 parent.map.CopyTo (map, 0);
2032 for (int i = start; i < Count; i++) {
2033 LocalInfo li = locals [i-start];
2035 if (li.VariableType == null)
2038 map [i] = li.VariableInfo = new VariableInfo (li, Length);
2039 Length += map [i].Length;
2044 // Returns the VariableInfo for variable @index or null if we don't need to
2045 // compute assignment info for this variable.
2047 public VariableInfo this [int index] {
2056 public override string ToString ()
2058 return String.Format ("VariableMap ({0}:{1})", Count, Length);
2063 // This is a special bit vector which can inherit from another bit vector doing a
2064 // copy-on-write strategy. The inherited vector may have a smaller size than the
2067 public class MyBitVector {
2068 public readonly int Count;
2069 public readonly MyBitVector InheritsFrom;
2074 public MyBitVector (int Count)
2075 : this (null, Count)
2078 public MyBitVector (MyBitVector InheritsFrom, int Count)
2080 this.InheritsFrom = InheritsFrom;
2085 // Checks whether this bit vector has been modified. After setting this to true,
2086 // we won't use the inherited vector anymore, but our own copy of it.
2088 public bool IsDirty {
2095 initialize_vector ();
2100 // Get/set bit `index' in the bit vector.
2102 public bool this [int index]
2106 throw new ArgumentOutOfRangeException ();
2108 // We're doing a "copy-on-write" strategy here; as long
2109 // as nobody writes to the array, we can use our parent's
2110 // copy instead of duplicating the vector.
2113 return vector [index];
2114 else if (InheritsFrom != null) {
2115 BitArray inherited = InheritsFrom.Vector;
2117 if (index < inherited.Count)
2118 return inherited [index];
2127 throw new ArgumentOutOfRangeException ();
2129 // Only copy the vector if we're actually modifying it.
2131 if (this [index] != value) {
2132 initialize_vector ();
2134 vector [index] = value;
2140 // If you explicitly convert the MyBitVector to a BitArray, you will get a deep
2141 // copy of the bit vector.
2143 public static explicit operator BitArray (MyBitVector vector)
2145 vector.initialize_vector ();
2146 return vector.Vector;
2150 // Performs an `or' operation on the bit vector. The `new_vector' may have a
2151 // different size than the current one.
2153 public void Or (MyBitVector new_vector)
2155 BitArray new_array = new_vector.Vector;
2157 initialize_vector ();
2160 if (vector.Count < new_array.Count)
2161 upper = vector.Count;
2163 upper = new_array.Count;
2165 for (int i = 0; i < upper; i++)
2166 vector [i] = vector [i] | new_array [i];
2170 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
2171 // a different size than the current one.
2173 public void And (MyBitVector new_vector)
2175 BitArray new_array = new_vector.Vector;
2177 initialize_vector ();
2180 if (vector.Count < new_array.Count)
2181 lower = upper = vector.Count;
2183 lower = new_array.Count;
2184 upper = vector.Count;
2187 for (int i = 0; i < lower; i++)
2188 vector [i] = vector [i] & new_array [i];
2190 for (int i = lower; i < upper; i++)
2194 public static void And (ref MyBitVector target, MyBitVector vector)
2197 target.And (vector);
2199 target = vector.Clone ();
2202 public static void Or (ref MyBitVector target, MyBitVector vector)
2207 target = vector.Clone ();
2211 // This does a deep copy of the bit vector.
2213 public MyBitVector Clone ()
2215 MyBitVector retval = new MyBitVector (Count);
2217 retval.Vector = Vector;
2226 else if (!is_dirty && (InheritsFrom != null))
2227 return InheritsFrom.Vector;
2229 initialize_vector ();
2235 initialize_vector ();
2237 for (int i = 0; i < System.Math.Min (vector.Count, value.Count); i++)
2238 vector [i] = value [i];
2242 void initialize_vector ()
2247 vector = new BitArray (Count, false);
2248 if (InheritsFrom != null)
2249 Vector = InheritsFrom.Vector;
2254 public override string ToString ()
2256 StringBuilder sb = new StringBuilder ("{");
2258 BitArray vector = Vector;
2261 for (int i = 0; i < vector.Count; i++) {
2262 sb.Append (vector [i] ? "1" : "0");
2266 return sb.ToString ();