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;
19 public enum TriState : byte {
20 // Never < Sometimes < Always
27 // A new instance of this class is created every time a new block is resolved
28 // and if there's branching in the block's control flow.
30 public abstract class FlowBranching
33 // The type of a FlowBranching.
35 public enum BranchingType : byte {
36 // Normal (conditional or toplevel) block.
45 // The statement embedded inside a loop
48 // part of a block headed by a jump target
60 // The toplevel block of a function
65 // The type of one sibling of a branching.
67 public enum SiblingType : byte {
76 public sealed class Reachability
78 TriState returns, throws, barrier;
80 public TriState Returns {
81 get { return returns; }
83 public TriState Throws {
84 get { return throws; }
86 public TriState Barrier {
87 get { return barrier; }
90 Reachability (TriState returns, TriState throws, TriState barrier)
92 this.returns = returns;
94 this.barrier = barrier;
97 public Reachability Clone ()
99 return new Reachability (returns, throws, barrier);
102 public static TriState TriState_Meet (TriState a, TriState b)
104 // (1) if both are Never, return Never
105 // (2) if both are Always, return Always
106 // (3) otherwise, return Sometimes
107 // note that (3) => (3') if both are Sometimes, return Sometimes
108 return a == b ? a : TriState.Sometimes;
111 public static TriState TriState_Max (TriState a, TriState b)
113 return ((byte) a > (byte) b) ? a : b;
116 public void Meet (Reachability b)
118 if ((AlwaysReturns && b.AlwaysHasBarrier) || (AlwaysHasBarrier && b.AlwaysReturns))
119 returns = TriState.Always;
121 returns = TriState_Meet (returns, b.returns);
123 throws = TriState_Meet (throws, b.throws);
124 barrier = TriState_Meet (barrier, b.barrier);
127 public void Or (Reachability b)
129 returns = TriState_Max (returns, b.returns);
130 throws = TriState_Max (throws, b.throws);
131 barrier = TriState_Max (barrier, b.barrier);
134 public static Reachability Always ()
136 return new Reachability (TriState.Never, TriState.Never, TriState.Never);
139 TriState Unreachable {
140 get { return TriState_Max (returns, TriState_Max (throws, barrier)); }
145 TriState unreachable = Unreachable;
146 if (unreachable == TriState.Sometimes)
147 return TriState.Sometimes;
148 return unreachable == TriState.Always ? TriState.Never : TriState.Always;
152 public bool AlwaysReturns {
153 get { return returns == TriState.Always; }
156 public bool AlwaysThrows {
157 get { return throws == TriState.Always; }
160 public bool AlwaysHasBarrier {
161 get { return barrier == TriState.Always; }
164 public bool IsUnreachable {
165 get { return Unreachable == TriState.Always; }
168 public void SetReturns ()
170 returns = TriState.Always;
173 public void SetThrows ()
175 throws = TriState.Always;
178 public void SetBarrier ()
180 barrier = TriState.Always;
183 static string ShortName (TriState returns)
188 case TriState.Sometimes:
195 public override string ToString ()
197 return String.Format ("[{0}:{1}:{2}:{3}]",
198 ShortName (returns), ShortName (throws), ShortName (barrier),
199 ShortName (Reachable));
203 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
206 case BranchingType.Exception:
207 case BranchingType.Labeled:
208 case BranchingType.Toplevel:
209 throw new InvalidOperationException ();
211 case BranchingType.Switch:
212 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
214 case BranchingType.SwitchSection:
215 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
217 case BranchingType.Block:
218 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
220 case BranchingType.Loop:
221 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
223 case BranchingType.Embedded:
224 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
227 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
232 // The type of this flow branching.
234 public readonly BranchingType Type;
237 // The block this branching is contained in. This may be null if it's not
238 // a top-level block and it doesn't declare any local variables.
240 public readonly Block Block;
243 // The parent of this branching or null if this is the top-block.
245 public readonly FlowBranching Parent;
248 // Start-Location of this flow branching.
250 public readonly Location Location;
252 protected VariableMap param_map, local_map;
254 static int next_id = 0;
258 // The vector contains a BitArray with information about which local variables
259 // and parameters are already initialized at the current code position.
261 public class UsageVector {
263 // The type of this branching.
265 public readonly SiblingType Type;
268 // Start location of this branching.
270 public Location Location;
273 // This is only valid for SwitchSection, Try, Catch and Finally.
275 public readonly Block Block;
278 // The number of parameters in this block.
280 public readonly int CountParameters;
283 // The number of locals in this block.
285 public readonly int CountLocals;
288 // If not null, then we inherit our state from this vector and do a
289 // copy-on-write. If null, then we're the first sibling in a top-level
290 // block and inherit from the empty vector.
292 public readonly UsageVector InheritsFrom;
295 // This is used to construct a list of UsageVector's.
297 public UsageVector Next;
302 MyBitVector locals, parameters;
303 Reachability reachability;
305 static int next_id = 0;
309 // Normally, you should not use any of these constructors.
311 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_params, int num_locals)
316 this.InheritsFrom = parent;
317 this.CountParameters = num_params;
318 this.CountLocals = num_locals;
320 locals = num_locals == 0
322 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
324 parameters = num_params == 0
326 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.parameters, num_params);
328 reachability = parent == null ? Reachability.Always () : parent.Reachability.Clone ();
333 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
334 : this (type, parent, block, loc, parent.CountParameters, parent.CountLocals)
337 public UsageVector (MyBitVector parameters, MyBitVector locals, Reachability reachability, Block block, Location loc)
339 this.Type = SiblingType.Block;
343 this.reachability = reachability;
344 this.parameters = parameters;
345 this.locals = locals;
351 // This does a deep copy of the usage vector.
353 public UsageVector Clone ()
355 UsageVector retval = new UsageVector (Type, null, Block, Location, CountParameters, CountLocals);
357 retval.locals = locals.Clone ();
358 retval.parameters = parameters.Clone ();
359 retval.reachability = reachability.Clone ();
364 public bool IsAssigned (VariableInfo var, bool ignoreReachability)
366 if (!ignoreReachability && !var.IsParameter && Reachability.IsUnreachable)
369 return var.IsAssigned (var.IsParameter ? parameters : locals);
372 public void SetAssigned (VariableInfo var)
374 if (!var.IsParameter && Reachability.IsUnreachable)
377 var.SetAssigned (var.IsParameter ? parameters : locals);
380 public bool IsFieldAssigned (VariableInfo var, string name)
382 if (!var.IsParameter && Reachability.IsUnreachable)
385 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
388 public void SetFieldAssigned (VariableInfo var, string name)
390 if (!var.IsParameter && Reachability.IsUnreachable)
393 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
396 public Reachability Reachability {
397 get { return reachability; }
400 public void Return ()
402 if (!reachability.IsUnreachable)
403 reachability.SetReturns ();
408 if (!reachability.IsUnreachable) {
409 reachability.SetThrows ();
410 reachability.SetBarrier ();
416 if (!reachability.IsUnreachable)
417 reachability.SetBarrier ();
420 public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
422 if (sibling_list.Next == null)
425 MyBitVector locals = null;
426 MyBitVector parameters = null;
427 Reachability reachability = null;
429 for (UsageVector child = sibling_list; child != null; child = child.Next) {
430 Report.Debug (2, " MERGING SIBLING ", reachability, child);
432 if (reachability == null)
433 reachability = child.Reachability.Clone ();
435 reachability.Meet (child.Reachability);
437 // A local variable is initialized after a flow branching if it
438 // has been initialized in all its branches which do neither
439 // always return or always throw an exception.
441 // If a branch may return, but does not always return, then we
442 // can treat it like a never-returning branch here: control will
443 // only reach the code position after the branching if we did not
446 // It's important to distinguish between always and sometimes
447 // returning branches here:
450 // 2 if (something) {
454 // 6 Console.WriteLine (a);
456 // The if block in lines 3-4 always returns, so we must not look
457 // at the initialization of `a' in line 4 - thus it'll still be
458 // uninitialized in line 6.
460 // On the other hand, the following is allowed:
467 // 6 Console.WriteLine (a);
469 // Here, `a' is initialized in line 3 and we must not look at
470 // line 5 since it always returns.
472 bool unreachable = child.Reachability.IsUnreachable;
474 Report.Debug (2, " MERGING SIBLING #1", reachability,
475 child.Type, child.Reachability.IsUnreachable, unreachable);
478 MyBitVector.And (ref locals, child.locals);
480 // An `out' parameter must be assigned in all branches which do
481 // not always throw an exception.
482 if (!child.Reachability.AlwaysThrows)
483 MyBitVector.And (ref parameters, child.parameters);
485 Report.Debug (2, " MERGING SIBLING #2", parameters, locals);
488 if (reachability == null)
489 throw new InternalErrorException ("Cannot happen: the loop above runs at least twice");
491 return new UsageVector (parameters, locals, reachability, null, loc);
495 // Merges a child branching.
497 public UsageVector MergeChild (UsageVector child, bool overwrite)
499 Report.Debug (2, " MERGING CHILD EFFECTS", this, child, reachability, Type);
501 Reachability new_r = child.Reachability;
504 // We've now either reached the point after the branching or we will
505 // never get there since we always return or always throw an exception.
507 // If we can reach the point after the branching, mark all locals and
508 // parameters as initialized which have been initialized in all branches
509 // we need to look at (see above).
512 if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
513 Report.Error (163, Location,
514 "Control cannot fall through from one " +
515 "case label to another");
519 MyBitVector.Or (ref locals, child.locals);
520 MyBitVector.Or (ref parameters, child.parameters);
523 reachability = new_r.Clone ();
525 reachability.Or (new_r);
530 public void MergeOrigins (UsageVector o_vectors)
532 Report.Debug (1, " MERGING BREAK ORIGINS", this);
534 if (o_vectors == null)
537 if (reachability.IsUnreachable) {
539 locals.SetAll (true);
540 if (parameters != null)
541 parameters.SetAll (true);
544 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
545 Report.Debug (1, " MERGING BREAK ORIGIN", vector);
546 MyBitVector.And (ref locals, vector.locals);
547 MyBitVector.And (ref parameters, vector.parameters);
548 reachability.Meet (vector.Reachability);
551 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
558 public override string ToString ()
560 return String.Format ("Vector ({0},{1},{2}-{3}-{4})", Type, id, reachability, parameters, locals);
565 // Creates a new flow branching which is contained in `parent'.
566 // You should only pass non-null for the `block' argument if this block
567 // introduces any new variables - in this case, we need to create a new
568 // usage vector with a different size than our parent's one.
570 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
571 Block block, Location loc)
581 param_map = Block.ParameterMap;
582 local_map = Block.LocalMap;
584 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
585 vector = new UsageVector (
586 stype, parent_vector, Block, loc,
587 param_map.Length, local_map.Length);
589 param_map = Parent.param_map;
590 local_map = Parent.local_map;
591 vector = new UsageVector (
592 stype, Parent.CurrentUsageVector, null, loc);
598 public abstract UsageVector CurrentUsageVector {
603 // Creates a sibling of the current usage vector.
605 public virtual void CreateSibling (Block block, SiblingType type)
607 UsageVector vector = new UsageVector (
608 type, Parent.CurrentUsageVector, block, Location);
611 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
614 public void CreateSibling ()
616 CreateSibling (null, SiblingType.Conditional);
619 protected abstract void AddSibling (UsageVector uv);
621 protected abstract UsageVector Merge ();
624 // Merge a child branching.
626 public UsageVector MergeChild (FlowBranching child)
628 bool overwrite = child.Type == BranchingType.Labeled ||
629 (child.Type == BranchingType.Block && child.Block.Implicit);
630 Report.Debug (2, " MERGING CHILD", this, child);
631 UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), overwrite);
632 Report.Debug (2, " MERGING CHILD DONE", this, result);
636 public virtual bool InTryWithCatch ()
638 return Parent.InTryWithCatch ();
641 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
642 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
644 return Parent.AddBreakOrigin (vector, loc);
647 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
648 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
650 return Parent.AddContinueOrigin (vector, loc);
653 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
654 public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
656 return Parent.AddReturnOrigin (vector, loc);
659 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
660 public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
662 return Parent.AddGotoOrigin (vector, goto_stmt);
665 public virtual void StealFinallyClauses (ref ArrayList list)
667 Parent.StealFinallyClauses (ref list);
670 public bool IsAssigned (VariableInfo vi)
672 return CurrentUsageVector.IsAssigned (vi, false);
675 public bool IsFieldAssigned (VariableInfo vi, string field_name)
677 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
680 public void SetAssigned (VariableInfo vi)
682 CurrentUsageVector.SetAssigned (vi);
685 public void SetFieldAssigned (VariableInfo vi, string name)
687 CurrentUsageVector.SetFieldAssigned (vi, name);
690 public override string ToString ()
692 StringBuilder sb = new StringBuilder ();
693 sb.Append (GetType ());
701 sb.Append (Block.ID);
703 sb.Append (Block.StartLocation);
706 // sb.Append (Siblings.Length);
707 // sb.Append (" - ");
708 sb.Append (CurrentUsageVector);
710 return sb.ToString ();
714 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
718 public class FlowBranchingBlock : FlowBranching
720 UsageVector sibling_list = null;
722 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
723 SiblingType stype, Block block, Location loc)
724 : base (parent, type, stype, block, loc)
727 public override UsageVector CurrentUsageVector {
728 get { return sibling_list; }
731 protected override void AddSibling (UsageVector sibling)
733 sibling.Next = sibling_list;
734 sibling_list = sibling;
737 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
739 LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
741 return Parent.AddGotoOrigin (vector, goto_stmt);
744 goto_stmt.SetResolvedTarget (stmt);
745 stmt.AddUsageVector (vector);
749 protected override UsageVector Merge ()
751 Report.Debug (2, " MERGING SIBLINGS", Name);
752 UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
753 Report.Debug (2, " MERGING SIBLINGS DONE", Name, vector);
758 public class FlowBranchingBreakable : FlowBranchingBlock
760 UsageVector break_origins;
762 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
763 : base (parent, type, stype, block, loc)
766 public override bool AddBreakOrigin (UsageVector vector, Location loc)
768 vector = vector.Clone ();
769 vector.Next = break_origins;
770 break_origins = vector;
774 protected override UsageVector Merge ()
776 UsageVector vector = base.Merge ();
777 vector.MergeOrigins (break_origins);
782 public class FlowBranchingContinuable : FlowBranchingBlock
784 UsageVector continue_origins;
786 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
787 : base (parent, type, stype, block, loc)
790 public override bool AddContinueOrigin (UsageVector vector, Location loc)
792 vector = vector.Clone ();
793 vector.Next = continue_origins;
794 continue_origins = vector;
798 protected override UsageVector Merge ()
800 UsageVector vector = base.Merge ();
801 vector.MergeOrigins (continue_origins);
806 public class FlowBranchingLabeled : FlowBranchingBlock
808 LabeledStatement stmt;
811 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
812 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
815 CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
816 actual = CurrentUsageVector.Clone ();
818 // stand-in for backward jumps
819 CurrentUsageVector.Reachability.Meet (Reachability.Always ());
822 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
824 if (goto_stmt.Target != stmt.Name)
825 return Parent.AddGotoOrigin (vector, goto_stmt);
828 goto_stmt.SetResolvedTarget (stmt);
829 actual.MergeOrigins (vector.Clone ());
834 protected override UsageVector Merge ()
836 UsageVector vector = base.Merge ();
838 if (actual.Reachability.IsUnreachable)
839 Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
841 actual.MergeChild (vector, false);
846 public class FlowBranchingToplevel : FlowBranchingBlock
848 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
849 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
854 // Check whether all `out' parameters have been assigned.
856 void CheckOutParameters (UsageVector vector, Location loc)
858 for (int i = 0; i < param_map.Count; i++) {
859 VariableInfo var = param_map [i];
864 if (vector.IsAssigned (var, false))
867 Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
872 public override bool InTryWithCatch ()
877 public override bool AddBreakOrigin (UsageVector vector, Location loc)
879 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
883 public override bool AddContinueOrigin (UsageVector vector, Location loc)
885 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
889 public override bool AddReturnOrigin (UsageVector vector, Location loc)
891 CheckOutParameters (vector, loc);
895 public override void StealFinallyClauses (ref ArrayList list)
900 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
902 string name = goto_stmt.Target;
903 LabeledStatement s = Block.LookupLabel (name);
905 throw new InternalErrorException ("Shouldn't get here");
907 if (Parent == null) {
908 Report.Error (159, goto_stmt.loc, "No such label `{0}' in this scope", name);
912 int errors = Report.Errors;
913 Parent.AddGotoOrigin (vector, goto_stmt);
914 if (errors == Report.Errors)
915 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
919 public Reachability End ()
921 UsageVector result = Merge ();
923 Report.Debug (4, "MERGE TOP BLOCK", Location, result);
925 if (!result.Reachability.AlwaysThrows && !result.Reachability.AlwaysHasBarrier)
926 CheckOutParameters (result, Location);
928 return result.Reachability;
932 public class FlowBranchingException : FlowBranching
934 ExceptionStatement stmt;
935 UsageVector current_vector;
936 UsageVector catch_vectors;
937 UsageVector finally_vector;
939 UsageVector break_origins;
940 UsageVector continue_origins;
941 UsageVector return_origins;
942 GotoOrigin goto_origins;
945 public GotoOrigin Next;
946 public Goto GotoStmt;
947 public UsageVector Vector;
949 public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
952 GotoStmt = goto_stmt;
959 public FlowBranchingException (FlowBranching parent,
960 ExceptionStatement stmt)
961 : base (parent, BranchingType.Exception, SiblingType.Try,
965 this.emit_finally = true;
968 protected override void AddSibling (UsageVector sibling)
970 switch (sibling.Type) {
971 case SiblingType.Try:
972 case SiblingType.Catch:
973 sibling.Next = catch_vectors;
974 catch_vectors = sibling;
976 case SiblingType.Finally:
977 finally_vector = sibling;
980 throw new InvalidOperationException ();
982 current_vector = sibling;
985 public override UsageVector CurrentUsageVector {
986 get { return current_vector; }
989 public override bool InTryWithCatch ()
991 if (finally_vector == null) {
993 if (t != null && t.HasCatch)
997 return base.InTryWithCatch ();
1000 public override bool AddBreakOrigin (UsageVector vector, Location loc)
1002 if (finally_vector != null) {
1003 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1005 vector = vector.Clone ();
1006 vector.Location = loc;
1007 vector.Next = break_origins;
1008 break_origins = vector;
1013 public override bool AddContinueOrigin (UsageVector vector, Location loc)
1015 if (finally_vector != null) {
1016 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1018 vector = vector.Clone ();
1019 vector.Location = loc;
1020 vector.Next = continue_origins;
1021 continue_origins = vector;
1026 public override bool AddReturnOrigin (UsageVector vector, Location loc)
1028 if (finally_vector != null) {
1029 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1031 vector = vector.Clone ();
1032 vector.Location = loc;
1033 vector.Next = return_origins;
1034 return_origins = vector;
1039 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
1041 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
1043 throw new InternalErrorException ("Shouldn't get here");
1045 if (finally_vector != null)
1046 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
1048 goto_origins = new GotoOrigin (vector.Clone (), goto_stmt, goto_origins);
1052 public override void StealFinallyClauses (ref ArrayList list)
1055 list = new ArrayList ();
1057 emit_finally = false;
1058 base.StealFinallyClauses (ref list);
1061 public bool EmitFinally {
1062 get { return emit_finally; }
1065 protected override UsageVector Merge ()
1067 Report.Debug (2, " MERGING TRY/CATCH", Name);
1068 UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
1069 Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
1071 if (finally_vector != null)
1072 vector.MergeChild (finally_vector, false);
1074 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
1075 if (finally_vector != null)
1076 origin.MergeChild (finally_vector, false);
1077 if (!origin.Reachability.IsUnreachable)
1078 Parent.AddBreakOrigin (origin, origin.Location);
1081 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
1082 if (finally_vector != null)
1083 origin.MergeChild (finally_vector, false);
1084 if (!origin.Reachability.IsUnreachable)
1085 Parent.AddContinueOrigin (origin, origin.Location);
1088 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
1089 if (finally_vector != null)
1090 origin.MergeChild (finally_vector, false);
1091 if (!origin.Reachability.IsUnreachable)
1092 Parent.AddReturnOrigin (origin, origin.Location);
1095 for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
1096 if (finally_vector != null)
1097 origin.Vector.MergeChild (finally_vector, false);
1098 if (!origin.Vector.Reachability.IsUnreachable)
1099 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
1107 // This is used by the flow analysis code to keep track of the type of local variables
1110 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1111 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1112 // you can only assign the whole variable as such.
1114 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1115 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1116 // one bit for each of its fields.
1118 // This class computes this `layout' for each type.
1120 public class TypeInfo
1122 public readonly Type Type;
1125 // Total number of bits a variable of this type consumes in the flow vector.
1127 public readonly int TotalLength;
1130 // Number of bits the simple fields of a variable of this type consume
1131 // in the flow vector.
1133 public readonly int Length;
1136 // This is only used by sub-structs.
1138 public readonly int Offset;
1141 // If this is a struct.
1143 public readonly bool IsStruct;
1146 // If this is a struct, all fields which are structs theirselves.
1148 public TypeInfo[] SubStructInfo;
1150 protected readonly StructInfo struct_info;
1151 private static Hashtable type_hash = new Hashtable ();
1153 public static TypeInfo GetTypeInfo (Type type)
1155 TypeInfo info = (TypeInfo) type_hash [type];
1159 info = new TypeInfo (type);
1160 type_hash.Add (type, info);
1164 public static TypeInfo GetTypeInfo (TypeContainer tc)
1166 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1170 info = new TypeInfo (tc);
1171 type_hash.Add (tc.TypeBuilder, info);
1175 private TypeInfo (Type type)
1179 struct_info = StructInfo.GetStructInfo (type);
1180 if (struct_info != null) {
1181 Length = struct_info.Length;
1182 TotalLength = struct_info.TotalLength;
1183 SubStructInfo = struct_info.StructFields;
1192 private TypeInfo (TypeContainer tc)
1194 this.Type = tc.TypeBuilder;
1196 struct_info = StructInfo.GetStructInfo (tc);
1197 if (struct_info != null) {
1198 Length = struct_info.Length;
1199 TotalLength = struct_info.TotalLength;
1200 SubStructInfo = struct_info.StructFields;
1209 protected TypeInfo (StructInfo struct_info, int offset)
1211 this.struct_info = struct_info;
1212 this.Offset = offset;
1213 this.Length = struct_info.Length;
1214 this.TotalLength = struct_info.TotalLength;
1215 this.SubStructInfo = struct_info.StructFields;
1216 this.Type = struct_info.Type;
1217 this.IsStruct = true;
1220 public int GetFieldIndex (string name)
1222 if (struct_info == null)
1225 return struct_info [name];
1228 public TypeInfo GetSubStruct (string name)
1230 if (struct_info == null)
1233 return struct_info.GetStructField (name);
1237 // A struct's constructor must always assign all fields.
1238 // This method checks whether it actually does so.
1240 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1242 if (struct_info == null)
1246 for (int i = 0; i < struct_info.Count; i++) {
1247 FieldInfo field = struct_info.Fields [i];
1249 if (!branching.IsFieldAssigned (vi, field.Name)) {
1250 Report.Error (171, loc,
1251 "Field `{0}' must be fully assigned before control leaves the constructor",
1252 TypeManager.GetFullNameSignature (field));
1260 public override string ToString ()
1262 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1263 Type, Offset, Length, TotalLength);
1266 protected class StructInfo {
1267 public readonly Type Type;
1268 public readonly FieldInfo[] Fields;
1269 public readonly TypeInfo[] StructFields;
1270 public readonly int Count;
1271 public readonly int CountPublic;
1272 public readonly int CountNonPublic;
1273 public readonly int Length;
1274 public readonly int TotalLength;
1275 public readonly bool HasStructFields;
1277 private static Hashtable field_type_hash = new Hashtable ();
1278 private Hashtable struct_field_hash;
1279 private Hashtable field_hash;
1281 protected bool InTransit = false;
1283 // Private constructor. To save memory usage, we only need to create one instance
1284 // of this class per struct type.
1285 private StructInfo (Type type)
1289 field_type_hash.Add (type, this);
1291 if (type is TypeBuilder) {
1292 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1294 ArrayList fields = null;
1298 ArrayList public_fields = new ArrayList ();
1299 ArrayList non_public_fields = new ArrayList ();
1301 if (fields != null) {
1302 foreach (FieldMember field in fields) {
1303 if ((field.ModFlags & Modifiers.STATIC) != 0)
1305 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1306 public_fields.Add (field.FieldBuilder);
1308 non_public_fields.Add (field.FieldBuilder);
1312 CountPublic = public_fields.Count;
1313 CountNonPublic = non_public_fields.Count;
1314 Count = CountPublic + CountNonPublic;
1316 Fields = new FieldInfo [Count];
1317 public_fields.CopyTo (Fields, 0);
1318 non_public_fields.CopyTo (Fields, CountPublic);
1320 FieldInfo[] public_fields = type.GetFields (
1321 BindingFlags.Instance|BindingFlags.Public);
1322 FieldInfo[] non_public_fields = type.GetFields (
1323 BindingFlags.Instance|BindingFlags.NonPublic);
1325 CountPublic = public_fields.Length;
1326 CountNonPublic = non_public_fields.Length;
1327 Count = CountPublic + CountNonPublic;
1329 Fields = new FieldInfo [Count];
1330 public_fields.CopyTo (Fields, 0);
1331 non_public_fields.CopyTo (Fields, CountPublic);
1334 struct_field_hash = new Hashtable ();
1335 field_hash = new Hashtable ();
1338 StructFields = new TypeInfo [Count];
1339 StructInfo[] sinfo = new StructInfo [Count];
1343 for (int i = 0; i < Count; i++) {
1344 FieldInfo field = (FieldInfo) Fields [i];
1346 sinfo [i] = GetStructInfo (field.FieldType);
1347 if (sinfo [i] == null)
1348 field_hash.Add (field.Name, ++Length);
1349 else if (sinfo [i].InTransit) {
1350 Report.Error (523, String.Format (
1351 "Struct member `{0}.{1}' of type `{2}' causes " +
1352 "a cycle in the structure layout",
1353 type, field.Name, sinfo [i].Type));
1361 TotalLength = Length + 1;
1362 for (int i = 0; i < Count; i++) {
1363 FieldInfo field = (FieldInfo) Fields [i];
1365 if (sinfo [i] == null)
1368 field_hash.Add (field.Name, TotalLength);
1370 HasStructFields = true;
1371 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1372 struct_field_hash.Add (field.Name, StructFields [i]);
1373 TotalLength += sinfo [i].TotalLength;
1377 public int this [string name] {
1379 if (field_hash.Contains (name))
1380 return (int) field_hash [name];
1386 public TypeInfo GetStructField (string name)
1388 return (TypeInfo) struct_field_hash [name];
1391 public static StructInfo GetStructInfo (Type type)
1393 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1394 TypeManager.IsBuiltinType (type))
1397 StructInfo info = (StructInfo) field_type_hash [type];
1401 return new StructInfo (type);
1404 public static StructInfo GetStructInfo (TypeContainer tc)
1406 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1410 return new StructInfo (tc.TypeBuilder);
1416 // This is used by the flow analysis code to store information about a single local variable
1417 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1418 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1419 // it has been assigned or not, but for structs, we need this information for each of its fields.
1421 public class VariableInfo {
1422 public readonly string Name;
1423 public readonly TypeInfo TypeInfo;
1426 // The bit offset of this variable in the flow vector.
1428 public readonly int Offset;
1431 // The number of bits this variable needs in the flow vector.
1432 // The first bit always specifies whether the variable as such has been assigned while
1433 // the remaining bits contain this information for each of a struct's fields.
1435 public readonly int Length;
1438 // If this is a parameter of local variable.
1440 public readonly bool IsParameter;
1442 public readonly LocalInfo LocalInfo;
1443 public readonly int ParameterIndex;
1445 readonly VariableInfo Parent;
1446 VariableInfo[] sub_info;
1448 protected VariableInfo (string name, Type type, int offset)
1451 this.Offset = offset;
1452 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1454 Length = TypeInfo.TotalLength;
1459 protected VariableInfo (VariableInfo parent, TypeInfo type)
1461 this.Name = parent.Name;
1462 this.TypeInfo = type;
1463 this.Offset = parent.Offset + type.Offset;
1464 this.Parent = parent;
1465 this.Length = type.TotalLength;
1467 this.IsParameter = parent.IsParameter;
1468 this.LocalInfo = parent.LocalInfo;
1469 this.ParameterIndex = parent.ParameterIndex;
1474 protected void Initialize ()
1476 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1477 if (sub_fields != null) {
1478 sub_info = new VariableInfo [sub_fields.Length];
1479 for (int i = 0; i < sub_fields.Length; i++) {
1480 if (sub_fields [i] != null)
1481 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1484 sub_info = new VariableInfo [0];
1487 public VariableInfo (LocalInfo local_info, int offset)
1488 : this (local_info.Name, local_info.VariableType, offset)
1490 this.LocalInfo = local_info;
1491 this.IsParameter = false;
1494 public VariableInfo (string name, Type type, int param_idx, int offset)
1495 : this (name, type, offset)
1497 this.ParameterIndex = param_idx;
1498 this.IsParameter = true;
1501 public bool IsAssigned (EmitContext ec)
1503 return !ec.DoFlowAnalysis ||
1504 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1505 ec.CurrentBranching.IsAssigned (this);
1508 public bool IsAssigned (EmitContext ec, Location loc)
1510 if (IsAssigned (ec))
1513 Report.Error (165, loc,
1514 "Use of unassigned local variable `" + Name + "'");
1515 ec.CurrentBranching.SetAssigned (this);
1519 public bool IsAssigned (MyBitVector vector)
1524 if (vector [Offset])
1527 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1528 if (vector [parent.Offset])
1531 // Return unless this is a struct.
1532 if (!TypeInfo.IsStruct)
1535 // Ok, so each field must be assigned.
1536 for (int i = 0; i < TypeInfo.Length; i++) {
1537 if (!vector [Offset + i + 1])
1541 // Ok, now check all fields which are structs.
1542 for (int i = 0; i < sub_info.Length; i++) {
1543 VariableInfo sinfo = sub_info [i];
1547 if (!sinfo.IsAssigned (vector))
1551 vector [Offset] = true;
1555 public void SetAssigned (EmitContext ec)
1557 if (ec.DoFlowAnalysis)
1558 ec.CurrentBranching.SetAssigned (this);
1561 public void SetAssigned (MyBitVector vector)
1563 vector [Offset] = true;
1566 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1568 if (!ec.DoFlowAnalysis ||
1569 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1570 ec.CurrentBranching.IsFieldAssigned (this, name))
1573 Report.Error (170, loc,
1574 "Use of possibly unassigned field `" + name + "'");
1575 ec.CurrentBranching.SetFieldAssigned (this, name);
1579 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1581 int field_idx = TypeInfo.GetFieldIndex (field_name);
1586 return vector [Offset + field_idx];
1589 public void SetFieldAssigned (EmitContext ec, string name)
1591 if (ec.DoFlowAnalysis)
1592 ec.CurrentBranching.SetFieldAssigned (this, name);
1595 public void SetFieldAssigned (MyBitVector vector, string field_name)
1597 int field_idx = TypeInfo.GetFieldIndex (field_name);
1602 vector [Offset + field_idx] = true;
1605 public VariableInfo GetSubStruct (string name)
1607 TypeInfo type = TypeInfo.GetSubStruct (name);
1612 return new VariableInfo (this, type);
1615 public override string ToString ()
1617 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1618 Name, TypeInfo, Offset, Length, IsParameter);
1623 // This is used by the flow code to hold the `layout' of the flow vector for
1624 // all locals and all parameters (ie. we create one instance of this class for the
1625 // locals and another one for the params).
1627 public class VariableMap {
1629 // The number of variables in the map.
1631 public readonly int Count;
1634 // Total length of the flow vector for this map.
1636 public readonly int Length;
1640 public VariableMap (Parameters ip)
1642 Count = ip != null ? ip.Count : 0;
1644 // Dont bother allocating anything!
1650 for (int i = 0; i < Count; i++) {
1651 Parameter.Modifier mod = ip.ParameterModifier (i);
1653 if ((mod & Parameter.Modifier.OUT) != Parameter.Modifier.OUT)
1656 // Dont allocate till we find an out var.
1658 map = new VariableInfo [Count];
1660 map [i] = new VariableInfo (ip.ParameterName (i),
1661 TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
1663 Length += map [i].Length;
1667 public VariableMap (LocalInfo[] locals)
1668 : this (null, locals)
1671 public VariableMap (VariableMap parent, LocalInfo[] locals)
1673 int offset = 0, start = 0;
1674 if (parent != null && parent.map != null) {
1675 offset = parent.Length;
1676 start = parent.Count;
1679 Count = locals.Length + start;
1684 map = new VariableInfo [Count];
1687 if (parent != null && parent.map != null) {
1688 parent.map.CopyTo (map, 0);
1691 for (int i = start; i < Count; i++) {
1692 LocalInfo li = locals [i-start];
1694 if (li.VariableType == null)
1697 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1698 Length += map [i].Length;
1703 // Returns the VariableInfo for variable @index or null if we don't need to
1704 // compute assignment info for this variable.
1706 public VariableInfo this [int index] {
1715 public override string ToString ()
1717 return String.Format ("VariableMap ({0}:{1})", Count, Length);
1722 // This is a special bit vector which can inherit from another bit vector doing a
1723 // copy-on-write strategy. The inherited vector may have a smaller size than the
1726 public class MyBitVector {
1727 public readonly int Count;
1728 public MyBitVector InheritsFrom;
1729 public static readonly MyBitVector Empty = new MyBitVector ();
1735 InheritsFrom = null;
1739 public MyBitVector (MyBitVector InheritsFrom, int Count)
1741 if (InheritsFrom != null) {
1742 while (InheritsFrom.InheritsFrom != null)
1743 InheritsFrom = InheritsFrom.InheritsFrom;
1744 if (InheritsFrom.Count >= Count && InheritsFrom.vector == null)
1745 InheritsFrom = null;
1748 this.InheritsFrom = InheritsFrom;
1753 // Get/set bit `index' in the bit vector.
1755 public bool this [int index]
1759 throw new ArgumentOutOfRangeException ();
1761 // We're doing a "copy-on-write" strategy here; as long
1762 // as nobody writes to the array, we can use our parent's
1763 // copy instead of duplicating the vector.
1766 return vector [index];
1767 if (InheritsFrom == null)
1769 if (index < InheritsFrom.Count)
1770 return InheritsFrom [index];
1775 // Only copy the vector if we're actually modifying it.
1776 if (this [index] != value) {
1778 initialize_vector ();
1779 vector [index] = value;
1785 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1786 // different size than the current one.
1788 private void Or (MyBitVector new_vector)
1790 int min = new_vector.Count;
1794 for (int i = 0; i < min; i++)
1795 this [i] |= new_vector [i];
1799 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
1800 // a different size than the current one.
1802 private void And (MyBitVector new_vector)
1804 int min = new_vector.Count;
1808 for (int i = 0; i < min; i++)
1809 this [i] &= new_vector [i];
1811 for (int i = min; i < Count; i++)
1815 public static void And (ref MyBitVector target, MyBitVector vector)
1820 target = vector.Clone ();
1822 target.And (vector);
1825 public static void Or (ref MyBitVector target, MyBitVector vector)
1830 target.SetAll (true);
1836 // This does a deep copy of the bit vector.
1838 public MyBitVector Clone ()
1842 MyBitVector retval = new MyBitVector (this, Count);
1843 retval.initialize_vector ();
1847 public void SetAll (bool value)
1849 InheritsFrom = value ? null : Empty;
1853 void initialize_vector ()
1855 if (InheritsFrom == null) {
1856 vector = new BitArray (Count, true);
1860 vector = new BitArray (Count, false);
1862 int min = InheritsFrom.Count;
1866 for (int i = 0; i < min; i++)
1867 vector [i] = InheritsFrom [i];
1869 InheritsFrom = null;
1872 StringBuilder Dump (StringBuilder sb)
1875 return InheritsFrom == null ? sb.Append ("/") : InheritsFrom.Dump (sb.Append ("="));
1876 for (int i = 0; i < Count; i++)
1877 sb.Append (this [i] ? "1" : "0");
1881 public override string ToString ()
1883 return Dump (new StringBuilder ("{")).Append ("}").ToString ();