2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
6 // Raja R Harinath (rharinath@novell.com)
8 // (C) 2001, 2002, 2003 Ximian, Inc.
13 using System.Collections;
14 using System.Reflection;
15 using System.Reflection.Emit;
16 using System.Diagnostics;
20 public enum TriState : byte {
21 // Never < Sometimes < Always
28 // A new instance of this class is created every time a new block is resolved
29 // and if there's branching in the block's control flow.
31 public abstract class FlowBranching
34 // The type of a FlowBranching.
36 public enum BranchingType : byte {
37 // Normal (conditional or toplevel) block.
46 // The statement embedded inside a loop
49 // part of a block headed by a jump target
61 // The toplevel block of a function
66 // The type of one sibling of a branching.
68 public enum SiblingType : byte {
77 public sealed class Reachability
79 TriState returns, barrier;
81 public TriState Returns {
82 get { return returns; }
84 public TriState Barrier {
85 get { return barrier; }
88 Reachability (TriState returns, TriState barrier)
90 this.returns = returns;
91 this.barrier = barrier;
94 public Reachability Clone ()
96 return new Reachability (returns, barrier);
99 public static TriState TriState_Meet (TriState a, TriState b)
101 // (1) if both are Never, return Never
102 // (2) if both are Always, return Always
103 // (3) otherwise, return Sometimes
104 // note that (3) => (3') if both are Sometimes, return Sometimes
105 return a == b ? a : TriState.Sometimes;
108 public static TriState TriState_Max (TriState a, TriState b)
110 return ((byte) a > (byte) b) ? a : b;
113 public void Meet (Reachability b)
115 if ((AlwaysReturns && b.AlwaysHasBarrier) || (AlwaysHasBarrier && b.AlwaysReturns))
116 returns = TriState.Always;
118 returns = TriState_Meet (returns, b.returns);
120 barrier = TriState_Meet (barrier, b.barrier);
123 public void Or (Reachability b)
125 returns = TriState_Max (returns, b.returns);
126 barrier = TriState_Max (barrier, b.barrier);
129 public static Reachability Always ()
131 return new Reachability (TriState.Never, TriState.Never);
134 TriState Unreachable {
135 get { return TriState_Max (returns, barrier); }
140 TriState unreachable = Unreachable;
141 if (unreachable == TriState.Sometimes)
142 return TriState.Sometimes;
143 return unreachable == TriState.Always ? TriState.Never : TriState.Always;
147 public bool AlwaysReturns {
148 get { return returns == TriState.Always; }
151 public bool AlwaysHasBarrier {
152 get { return barrier == TriState.Always; }
155 public bool IsUnreachable {
156 get { return Unreachable == TriState.Always; }
159 public void SetReturns ()
161 returns = TriState.Always;
164 public void SetBarrier ()
166 barrier = TriState.Always;
169 static string ShortName (TriState returns)
174 case TriState.Sometimes:
181 public override string ToString ()
183 return String.Format ("[{0}:{1}:{2}]",
184 ShortName (returns), ShortName (barrier), ShortName (Reachable));
188 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
191 case BranchingType.Exception:
192 case BranchingType.Labeled:
193 case BranchingType.Toplevel:
194 throw new InvalidOperationException ();
196 case BranchingType.Switch:
197 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
199 case BranchingType.SwitchSection:
200 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
202 case BranchingType.Block:
203 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
205 case BranchingType.Loop:
206 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
208 case BranchingType.Embedded:
209 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
212 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
217 // The type of this flow branching.
219 public readonly BranchingType Type;
222 // The block this branching is contained in. This may be null if it's not
223 // a top-level block and it doesn't declare any local variables.
225 public readonly Block Block;
228 // The parent of this branching or null if this is the top-block.
230 public readonly FlowBranching Parent;
233 // Start-Location of this flow branching.
235 public readonly Location Location;
237 protected VariableMap param_map, local_map;
239 static int next_id = 0;
243 // The vector contains a BitArray with information about which local variables
244 // and parameters are already initialized at the current code position.
246 public class UsageVector {
248 // The type of this branching.
250 public readonly SiblingType Type;
253 // Start location of this branching.
255 public Location Location;
258 // This is only valid for SwitchSection, Try, Catch and Finally.
260 public readonly Block Block;
263 // The number of parameters in this block.
265 public readonly int CountParameters;
268 // The number of locals in this block.
270 public readonly int CountLocals;
273 // If not null, then we inherit our state from this vector and do a
274 // copy-on-write. If null, then we're the first sibling in a top-level
275 // block and inherit from the empty vector.
277 public readonly UsageVector InheritsFrom;
280 // This is used to construct a list of UsageVector's.
282 public UsageVector Next;
287 MyBitVector locals, parameters;
288 Reachability reachability;
290 static int next_id = 0;
294 // Normally, you should not use any of these constructors.
296 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_params, int num_locals)
301 this.InheritsFrom = parent;
302 this.CountParameters = num_params;
303 this.CountLocals = num_locals;
305 locals = num_locals == 0
307 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
309 parameters = num_params == 0
311 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.parameters, num_params);
313 reachability = parent == null ? Reachability.Always () : parent.Reachability.Clone ();
318 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
319 : this (type, parent, block, loc, parent.CountParameters, parent.CountLocals)
322 public UsageVector (MyBitVector parameters, MyBitVector locals, Reachability reachability, Block block, Location loc)
324 this.Type = SiblingType.Block;
328 this.reachability = reachability;
329 this.parameters = parameters;
330 this.locals = locals;
336 // This does a deep copy of the usage vector.
338 public UsageVector Clone ()
340 UsageVector retval = new UsageVector (Type, null, Block, Location, CountParameters, CountLocals);
342 retval.locals = locals.Clone ();
343 retval.parameters = parameters.Clone ();
344 retval.reachability = reachability.Clone ();
349 public bool IsAssigned (VariableInfo var, bool ignoreReachability)
351 if (!ignoreReachability && !var.IsParameter && Reachability.IsUnreachable)
354 return var.IsAssigned (var.IsParameter ? parameters : locals);
357 public void SetAssigned (VariableInfo var)
359 if (!var.IsParameter && Reachability.IsUnreachable)
362 var.SetAssigned (var.IsParameter ? parameters : locals);
365 public bool IsFieldAssigned (VariableInfo var, string name)
367 if (!var.IsParameter && Reachability.IsUnreachable)
370 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
373 public void SetFieldAssigned (VariableInfo var, string name)
375 if (!var.IsParameter && Reachability.IsUnreachable)
378 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
381 public Reachability Reachability {
382 get { return reachability; }
385 public void Return ()
387 if (!reachability.IsUnreachable)
388 reachability.SetReturns ();
393 if (!reachability.IsUnreachable)
394 reachability.SetBarrier ();
397 public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
399 if (sibling_list.Next == null)
402 MyBitVector locals = null;
403 MyBitVector parameters = null;
404 Reachability reachability = sibling_list.Reachability.Clone ();
406 if (!sibling_list.Reachability.IsUnreachable) {
407 locals &= sibling_list.locals;
408 parameters &= sibling_list.parameters;
411 for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
412 reachability.Meet (child.Reachability);
414 if (!child.Reachability.IsUnreachable) {
415 locals &= child.locals;
416 parameters &= child.parameters;
420 return new UsageVector (parameters, locals, reachability, null, loc);
424 // Merges a child branching.
426 public UsageVector MergeChild (UsageVector child, bool overwrite)
428 Report.Debug (2, " MERGING CHILD EFFECTS", this, child, reachability, Type);
430 Reachability new_r = child.Reachability;
433 // We've now either reached the point after the branching or we will
434 // never get there since we always return or always throw an exception.
436 // If we can reach the point after the branching, mark all locals and
437 // parameters as initialized which have been initialized in all branches
438 // we need to look at (see above).
441 if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
442 Report.Error (163, Location,
443 "Control cannot fall through from one " +
444 "case label to another");
448 locals |= child.locals;
449 parameters |= child.parameters;
452 reachability = new_r.Clone ();
454 reachability.Or (new_r);
459 public void MergeOrigins (UsageVector o_vectors)
461 Report.Debug (1, " MERGING BREAK ORIGINS", this);
463 if (o_vectors == null)
466 if (reachability.IsUnreachable) {
468 locals.SetAll (true);
469 if (parameters != null)
470 parameters.SetAll (true);
473 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
474 Report.Debug (1, " MERGING BREAK ORIGIN", vector);
475 if (vector.Reachability.IsUnreachable)
477 locals &= vector.locals;
478 parameters &= vector.parameters;
479 reachability.Meet (vector.Reachability);
482 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
489 public override string ToString ()
491 return String.Format ("Vector ({0},{1},{2}-{3}-{4})", Type, id, reachability, parameters, locals);
496 // Creates a new flow branching which is contained in `parent'.
497 // You should only pass non-null for the `block' argument if this block
498 // introduces any new variables - in this case, we need to create a new
499 // usage vector with a different size than our parent's one.
501 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
502 Block block, Location loc)
512 param_map = Block.ParameterMap;
513 local_map = Block.LocalMap;
515 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
516 vector = new UsageVector (
517 stype, parent_vector, Block, loc,
518 param_map.Length, local_map.Length);
520 param_map = Parent.param_map;
521 local_map = Parent.local_map;
522 vector = new UsageVector (
523 stype, Parent.CurrentUsageVector, null, loc);
529 public abstract UsageVector CurrentUsageVector {
534 // Creates a sibling of the current usage vector.
536 public virtual void CreateSibling (Block block, SiblingType type)
538 UsageVector vector = new UsageVector (
539 type, Parent.CurrentUsageVector, block, Location);
542 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
545 public void CreateSibling ()
547 CreateSibling (null, SiblingType.Conditional);
550 protected abstract void AddSibling (UsageVector uv);
552 protected abstract UsageVector Merge ();
555 // Merge a child branching.
557 public UsageVector MergeChild (FlowBranching child)
559 bool overwrite = child.Type == BranchingType.Labeled ||
560 (child.Type == BranchingType.Block && child.Block.Implicit);
561 Report.Debug (2, " MERGING CHILD", this, child);
562 UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), overwrite);
563 Report.Debug (2, " MERGING CHILD DONE", this, result);
567 public virtual bool InTryWithCatch ()
569 return Parent.InTryWithCatch ();
572 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
573 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
575 return Parent.AddBreakOrigin (vector, loc);
578 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
579 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
581 return Parent.AddContinueOrigin (vector, loc);
584 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
585 public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
587 return Parent.AddReturnOrigin (vector, loc);
590 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
591 public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
593 return Parent.AddGotoOrigin (vector, goto_stmt);
596 public virtual void StealFinallyClauses (ref ArrayList list)
598 Parent.StealFinallyClauses (ref list);
601 public bool IsAssigned (VariableInfo vi)
603 return CurrentUsageVector.IsAssigned (vi, false);
606 public bool IsFieldAssigned (VariableInfo vi, string field_name)
608 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
611 public void SetAssigned (VariableInfo vi)
613 CurrentUsageVector.SetAssigned (vi);
616 public void SetFieldAssigned (VariableInfo vi, string name)
618 CurrentUsageVector.SetFieldAssigned (vi, name);
621 public override string ToString ()
623 StringBuilder sb = new StringBuilder ();
624 sb.Append (GetType ());
632 sb.Append (Block.ID);
634 sb.Append (Block.StartLocation);
637 // sb.Append (Siblings.Length);
638 // sb.Append (" - ");
639 sb.Append (CurrentUsageVector);
641 return sb.ToString ();
645 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
649 public class FlowBranchingBlock : FlowBranching
651 UsageVector sibling_list = null;
653 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
654 SiblingType stype, Block block, Location loc)
655 : base (parent, type, stype, block, loc)
658 public override UsageVector CurrentUsageVector {
659 get { return sibling_list; }
662 protected override void AddSibling (UsageVector sibling)
664 sibling.Next = sibling_list;
665 sibling_list = sibling;
668 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
670 LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
672 return Parent.AddGotoOrigin (vector, goto_stmt);
675 goto_stmt.SetResolvedTarget (stmt);
676 stmt.AddUsageVector (vector);
680 protected override UsageVector Merge ()
682 Report.Debug (2, " MERGING SIBLINGS", Name);
683 UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
684 Report.Debug (2, " MERGING SIBLINGS DONE", Name, vector);
689 public class FlowBranchingBreakable : FlowBranchingBlock
691 UsageVector break_origins;
693 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
694 : base (parent, type, stype, block, loc)
697 public override bool AddBreakOrigin (UsageVector vector, Location loc)
699 vector = vector.Clone ();
700 vector.Next = break_origins;
701 break_origins = vector;
705 protected override UsageVector Merge ()
707 UsageVector vector = base.Merge ();
708 vector.MergeOrigins (break_origins);
713 public class FlowBranchingContinuable : FlowBranchingBlock
715 UsageVector continue_origins;
717 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
718 : base (parent, type, stype, block, loc)
721 public override bool AddContinueOrigin (UsageVector vector, Location loc)
723 vector = vector.Clone ();
724 vector.Next = continue_origins;
725 continue_origins = vector;
729 protected override UsageVector Merge ()
731 UsageVector vector = base.Merge ();
732 vector.MergeOrigins (continue_origins);
737 public class FlowBranchingLabeled : FlowBranchingBlock
739 LabeledStatement stmt;
742 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
743 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
746 CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
747 actual = CurrentUsageVector.Clone ();
749 // stand-in for backward jumps
750 CurrentUsageVector.Reachability.Meet (Reachability.Always ());
753 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
755 if (goto_stmt.Target != stmt.Name)
756 return Parent.AddGotoOrigin (vector, goto_stmt);
759 goto_stmt.SetResolvedTarget (stmt);
760 actual.MergeOrigins (vector.Clone ());
765 protected override UsageVector Merge ()
767 UsageVector vector = base.Merge ();
769 if (actual.Reachability.IsUnreachable)
770 Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
772 actual.MergeChild (vector, false);
777 public class FlowBranchingToplevel : FlowBranchingBlock
779 UsageVector return_origins;
781 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
782 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
787 // Check whether all `out' parameters have been assigned.
789 void CheckOutParameters (UsageVector vector, Location loc)
791 if (vector.Reachability.IsUnreachable)
793 for (int i = 0; i < param_map.Count; i++) {
794 VariableInfo var = param_map [i];
799 if (vector.IsAssigned (var, false))
802 Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
807 public override bool InTryWithCatch ()
812 public override bool AddBreakOrigin (UsageVector vector, Location loc)
814 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
818 public override bool AddContinueOrigin (UsageVector vector, Location loc)
820 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
824 public override bool AddReturnOrigin (UsageVector vector, Location loc)
826 vector = vector.Clone ();
827 vector.Location = loc;
828 vector.Next = return_origins;
829 return_origins = vector;
833 public override void StealFinallyClauses (ref ArrayList list)
838 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
840 string name = goto_stmt.Target;
841 LabeledStatement s = Block.LookupLabel (name);
843 throw new InternalErrorException ("Shouldn't get here");
845 if (Parent == null) {
846 Report.Error (159, goto_stmt.loc, "No such label `{0}' in this scope", name);
850 int errors = Report.Errors;
851 Parent.AddGotoOrigin (vector, goto_stmt);
852 if (errors == Report.Errors)
853 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
857 protected override UsageVector Merge ()
859 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
860 CheckOutParameters (origin, origin.Location);
862 UsageVector vector = base.Merge ();
863 CheckOutParameters (vector, Block.loc);
864 // Note: we _do_not_ merge in the return origins
868 public Reachability End ()
870 return Merge ().Reachability;
874 public class FlowBranchingException : FlowBranching
876 ExceptionStatement stmt;
877 UsageVector current_vector;
878 UsageVector catch_vectors;
879 UsageVector finally_vector;
881 UsageVector break_origins;
882 UsageVector continue_origins;
883 UsageVector return_origins;
884 GotoOrigin goto_origins;
887 public GotoOrigin Next;
888 public Goto GotoStmt;
889 public UsageVector Vector;
891 public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
894 GotoStmt = goto_stmt;
901 public FlowBranchingException (FlowBranching parent,
902 ExceptionStatement stmt)
903 : base (parent, BranchingType.Exception, SiblingType.Try,
907 this.emit_finally = true;
910 protected override void AddSibling (UsageVector sibling)
912 switch (sibling.Type) {
913 case SiblingType.Try:
914 case SiblingType.Catch:
915 sibling.Next = catch_vectors;
916 catch_vectors = sibling;
918 case SiblingType.Finally:
919 finally_vector = sibling;
922 throw new InvalidOperationException ();
924 current_vector = sibling;
927 public override UsageVector CurrentUsageVector {
928 get { return current_vector; }
931 public override bool InTryWithCatch ()
933 if (finally_vector == null) {
935 if (t != null && t.HasCatch)
939 return base.InTryWithCatch ();
942 public override bool AddBreakOrigin (UsageVector vector, Location loc)
944 vector = vector.Clone ();
945 if (finally_vector != null) {
946 vector.MergeChild (finally_vector, false);
947 int errors = Report.Errors;
948 Parent.AddBreakOrigin (vector, loc);
949 if (errors == Report.Errors)
950 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
952 vector.Location = loc;
953 vector.Next = break_origins;
954 break_origins = vector;
959 public override bool AddContinueOrigin (UsageVector vector, Location loc)
961 vector = vector.Clone ();
962 if (finally_vector != null) {
963 vector.MergeChild (finally_vector, false);
964 int errors = Report.Errors;
965 Parent.AddContinueOrigin (vector, loc);
966 if (errors == Report.Errors)
967 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
969 vector.Location = loc;
970 vector.Next = continue_origins;
971 continue_origins = vector;
976 public override bool AddReturnOrigin (UsageVector vector, Location loc)
978 vector = vector.Clone ();
979 if (finally_vector != null) {
980 vector.MergeChild (finally_vector, false);
981 int errors = Report.Errors;
982 Parent.AddReturnOrigin (vector, loc);
983 if (errors == Report.Errors)
984 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
986 vector.Location = loc;
987 vector.Next = return_origins;
988 return_origins = vector;
993 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
995 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
997 throw new InternalErrorException ("Shouldn't get here");
999 vector = vector.Clone ();
1000 if (finally_vector != null) {
1001 vector.MergeChild (finally_vector, false);
1002 int errors = Report.Errors;
1003 Parent.AddGotoOrigin (vector, goto_stmt);
1004 if (errors == Report.Errors)
1005 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
1007 goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
1012 public override void StealFinallyClauses (ref ArrayList list)
1015 list = new ArrayList ();
1017 emit_finally = false;
1018 base.StealFinallyClauses (ref list);
1021 public bool EmitFinally {
1022 get { return emit_finally; }
1025 protected override UsageVector Merge ()
1027 Report.Debug (2, " MERGING TRY/CATCH", Name);
1028 UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
1029 Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
1031 if (finally_vector != null)
1032 vector.MergeChild (finally_vector, false);
1034 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
1035 if (finally_vector != null)
1036 origin.MergeChild (finally_vector, false);
1037 Parent.AddBreakOrigin (origin, origin.Location);
1040 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
1041 if (finally_vector != null)
1042 origin.MergeChild (finally_vector, false);
1043 Parent.AddContinueOrigin (origin, origin.Location);
1046 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
1047 if (finally_vector != null)
1048 origin.MergeChild (finally_vector, false);
1049 Parent.AddReturnOrigin (origin, origin.Location);
1052 for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
1053 if (finally_vector != null)
1054 origin.Vector.MergeChild (finally_vector, false);
1055 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
1063 // This is used by the flow analysis code to keep track of the type of local variables
1066 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1067 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1068 // you can only assign the whole variable as such.
1070 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1071 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1072 // one bit for each of its fields.
1074 // This class computes this `layout' for each type.
1076 public class TypeInfo
1078 public readonly Type Type;
1081 // Total number of bits a variable of this type consumes in the flow vector.
1083 public readonly int TotalLength;
1086 // Number of bits the simple fields of a variable of this type consume
1087 // in the flow vector.
1089 public readonly int Length;
1092 // This is only used by sub-structs.
1094 public readonly int Offset;
1097 // If this is a struct.
1099 public readonly bool IsStruct;
1102 // If this is a struct, all fields which are structs theirselves.
1104 public TypeInfo[] SubStructInfo;
1106 protected readonly StructInfo struct_info;
1107 private static Hashtable type_hash = new Hashtable ();
1109 public static TypeInfo GetTypeInfo (Type type)
1111 TypeInfo info = (TypeInfo) type_hash [type];
1115 info = new TypeInfo (type);
1116 type_hash.Add (type, info);
1120 public static TypeInfo GetTypeInfo (TypeContainer tc)
1122 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1126 info = new TypeInfo (tc);
1127 type_hash.Add (tc.TypeBuilder, info);
1131 private TypeInfo (Type type)
1135 struct_info = StructInfo.GetStructInfo (type);
1136 if (struct_info != null) {
1137 Length = struct_info.Length;
1138 TotalLength = struct_info.TotalLength;
1139 SubStructInfo = struct_info.StructFields;
1148 private TypeInfo (TypeContainer tc)
1150 this.Type = tc.TypeBuilder;
1152 struct_info = StructInfo.GetStructInfo (tc);
1153 if (struct_info != null) {
1154 Length = struct_info.Length;
1155 TotalLength = struct_info.TotalLength;
1156 SubStructInfo = struct_info.StructFields;
1165 protected TypeInfo (StructInfo struct_info, int offset)
1167 this.struct_info = struct_info;
1168 this.Offset = offset;
1169 this.Length = struct_info.Length;
1170 this.TotalLength = struct_info.TotalLength;
1171 this.SubStructInfo = struct_info.StructFields;
1172 this.Type = struct_info.Type;
1173 this.IsStruct = true;
1176 public int GetFieldIndex (string name)
1178 if (struct_info == null)
1181 return struct_info [name];
1184 public TypeInfo GetSubStruct (string name)
1186 if (struct_info == null)
1189 return struct_info.GetStructField (name);
1193 // A struct's constructor must always assign all fields.
1194 // This method checks whether it actually does so.
1196 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1198 if (struct_info == null)
1202 for (int i = 0; i < struct_info.Count; i++) {
1203 FieldInfo field = struct_info.Fields [i];
1205 if (!branching.IsFieldAssigned (vi, field.Name)) {
1206 Report.Error (171, loc,
1207 "Field `{0}' must be fully assigned before control leaves the constructor",
1208 TypeManager.GetFullNameSignature (field));
1216 public override string ToString ()
1218 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1219 Type, Offset, Length, TotalLength);
1222 protected class StructInfo {
1223 public readonly Type Type;
1224 public readonly FieldInfo[] Fields;
1225 public readonly TypeInfo[] StructFields;
1226 public readonly int Count;
1227 public readonly int CountPublic;
1228 public readonly int CountNonPublic;
1229 public readonly int Length;
1230 public readonly int TotalLength;
1231 public readonly bool HasStructFields;
1233 private static Hashtable field_type_hash = new Hashtable ();
1234 private Hashtable struct_field_hash;
1235 private Hashtable field_hash;
1237 protected bool InTransit = false;
1239 // Private constructor. To save memory usage, we only need to create one instance
1240 // of this class per struct type.
1241 private StructInfo (Type type)
1245 field_type_hash.Add (type, this);
1247 if (type is TypeBuilder) {
1248 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1250 ArrayList fields = null;
1254 ArrayList public_fields = new ArrayList ();
1255 ArrayList non_public_fields = new ArrayList ();
1257 if (fields != null) {
1258 foreach (FieldBase field in fields) {
1259 if ((field.ModFlags & Modifiers.STATIC) != 0)
1261 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1262 public_fields.Add (field.FieldBuilder);
1264 non_public_fields.Add (field.FieldBuilder);
1268 CountPublic = public_fields.Count;
1269 CountNonPublic = non_public_fields.Count;
1270 Count = CountPublic + CountNonPublic;
1272 Fields = new FieldInfo [Count];
1273 public_fields.CopyTo (Fields, 0);
1274 non_public_fields.CopyTo (Fields, CountPublic);
1276 } else if (type is GenericTypeParameterBuilder) {
1277 CountPublic = CountNonPublic = Count = 0;
1279 Fields = new FieldInfo [0];
1282 FieldInfo[] public_fields = type.GetFields (
1283 BindingFlags.Instance|BindingFlags.Public);
1284 FieldInfo[] non_public_fields = type.GetFields (
1285 BindingFlags.Instance|BindingFlags.NonPublic);
1287 CountPublic = public_fields.Length;
1288 CountNonPublic = non_public_fields.Length;
1289 Count = CountPublic + CountNonPublic;
1291 Fields = new FieldInfo [Count];
1292 public_fields.CopyTo (Fields, 0);
1293 non_public_fields.CopyTo (Fields, CountPublic);
1296 struct_field_hash = new Hashtable ();
1297 field_hash = new Hashtable ();
1300 StructFields = new TypeInfo [Count];
1301 StructInfo[] sinfo = new StructInfo [Count];
1305 for (int i = 0; i < Count; i++) {
1306 FieldInfo field = (FieldInfo) Fields [i];
1308 sinfo [i] = GetStructInfo (field.FieldType);
1309 if (sinfo [i] == null)
1310 field_hash.Add (field.Name, ++Length);
1311 else if (sinfo [i].InTransit) {
1312 Report.Error (523, String.Format (
1313 "Struct member `{0}.{1}' of type `{2}' causes " +
1314 "a cycle in the structure layout",
1315 type, field.Name, sinfo [i].Type));
1323 TotalLength = Length + 1;
1324 for (int i = 0; i < Count; i++) {
1325 FieldInfo field = (FieldInfo) Fields [i];
1327 if (sinfo [i] == null)
1330 field_hash.Add (field.Name, TotalLength);
1332 HasStructFields = true;
1333 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1334 struct_field_hash.Add (field.Name, StructFields [i]);
1335 TotalLength += sinfo [i].TotalLength;
1339 public int this [string name] {
1341 if (field_hash.Contains (name))
1342 return (int) field_hash [name];
1348 public TypeInfo GetStructField (string name)
1350 return (TypeInfo) struct_field_hash [name];
1353 public static StructInfo GetStructInfo (Type type)
1355 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1356 TypeManager.IsBuiltinType (type))
1359 StructInfo info = (StructInfo) field_type_hash [type];
1363 return new StructInfo (type);
1366 public static StructInfo GetStructInfo (TypeContainer tc)
1368 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1372 return new StructInfo (tc.TypeBuilder);
1378 // This is used by the flow analysis code to store information about a single local variable
1379 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1380 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1381 // it has been assigned or not, but for structs, we need this information for each of its fields.
1383 public class VariableInfo {
1384 public readonly string Name;
1385 public readonly TypeInfo TypeInfo;
1388 // The bit offset of this variable in the flow vector.
1390 public readonly int Offset;
1393 // The number of bits this variable needs in the flow vector.
1394 // The first bit always specifies whether the variable as such has been assigned while
1395 // the remaining bits contain this information for each of a struct's fields.
1397 public readonly int Length;
1400 // If this is a parameter of local variable.
1402 public readonly bool IsParameter;
1404 public readonly LocalInfo LocalInfo;
1405 public readonly int ParameterIndex;
1407 readonly VariableInfo Parent;
1408 VariableInfo[] sub_info;
1410 protected VariableInfo (string name, Type type, int offset)
1413 this.Offset = offset;
1414 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1416 Length = TypeInfo.TotalLength;
1421 protected VariableInfo (VariableInfo parent, TypeInfo type)
1423 this.Name = parent.Name;
1424 this.TypeInfo = type;
1425 this.Offset = parent.Offset + type.Offset;
1426 this.Parent = parent;
1427 this.Length = type.TotalLength;
1429 this.IsParameter = parent.IsParameter;
1430 this.LocalInfo = parent.LocalInfo;
1431 this.ParameterIndex = parent.ParameterIndex;
1436 protected void Initialize ()
1438 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1439 if (sub_fields != null) {
1440 sub_info = new VariableInfo [sub_fields.Length];
1441 for (int i = 0; i < sub_fields.Length; i++) {
1442 if (sub_fields [i] != null)
1443 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1446 sub_info = new VariableInfo [0];
1449 public VariableInfo (LocalInfo local_info, int offset)
1450 : this (local_info.Name, local_info.VariableType, offset)
1452 this.LocalInfo = local_info;
1453 this.IsParameter = false;
1456 public VariableInfo (string name, Type type, int param_idx, int offset)
1457 : this (name, type, offset)
1459 this.ParameterIndex = param_idx;
1460 this.IsParameter = true;
1463 public bool IsAssigned (EmitContext ec)
1465 return !ec.DoFlowAnalysis ||
1466 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1467 ec.CurrentBranching.IsAssigned (this);
1470 public bool IsAssigned (EmitContext ec, Location loc)
1472 if (IsAssigned (ec))
1475 Report.Error (165, loc,
1476 "Use of unassigned local variable `" + Name + "'");
1477 ec.CurrentBranching.SetAssigned (this);
1481 public bool IsAssigned (MyBitVector vector)
1486 if (vector [Offset])
1489 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1490 if (vector [parent.Offset])
1493 // Return unless this is a struct.
1494 if (!TypeInfo.IsStruct)
1497 // Ok, so each field must be assigned.
1498 for (int i = 0; i < TypeInfo.Length; i++) {
1499 if (!vector [Offset + i + 1])
1503 // Ok, now check all fields which are structs.
1504 for (int i = 0; i < sub_info.Length; i++) {
1505 VariableInfo sinfo = sub_info [i];
1509 if (!sinfo.IsAssigned (vector))
1513 vector [Offset] = true;
1517 public void SetAssigned (EmitContext ec)
1519 if (ec.DoFlowAnalysis)
1520 ec.CurrentBranching.SetAssigned (this);
1523 public void SetAssigned (MyBitVector vector)
1525 vector [Offset] = true;
1528 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1530 if (!ec.DoFlowAnalysis ||
1531 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1532 ec.CurrentBranching.IsFieldAssigned (this, name))
1535 Report.Error (170, loc,
1536 "Use of possibly unassigned field `" + name + "'");
1537 ec.CurrentBranching.SetFieldAssigned (this, name);
1541 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1543 int field_idx = TypeInfo.GetFieldIndex (field_name);
1548 return vector [Offset + field_idx];
1551 public void SetFieldAssigned (EmitContext ec, string name)
1553 if (ec.DoFlowAnalysis)
1554 ec.CurrentBranching.SetFieldAssigned (this, name);
1557 public void SetFieldAssigned (MyBitVector vector, string field_name)
1559 int field_idx = TypeInfo.GetFieldIndex (field_name);
1564 vector [Offset + field_idx] = true;
1567 public VariableInfo GetSubStruct (string name)
1569 TypeInfo type = TypeInfo.GetSubStruct (name);
1574 return new VariableInfo (this, type);
1577 public override string ToString ()
1579 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1580 Name, TypeInfo, Offset, Length, IsParameter);
1585 // This is used by the flow code to hold the `layout' of the flow vector for
1586 // all locals and all parameters (ie. we create one instance of this class for the
1587 // locals and another one for the params).
1589 public class VariableMap {
1591 // The number of variables in the map.
1593 public readonly int Count;
1596 // Total length of the flow vector for this map.
1598 public readonly int Length;
1602 public VariableMap (Parameters ip)
1604 Count = ip != null ? ip.Count : 0;
1606 // Dont bother allocating anything!
1612 for (int i = 0; i < Count; i++) {
1613 Parameter.Modifier mod = ip.ParameterModifier (i);
1615 if ((mod & Parameter.Modifier.OUT) != Parameter.Modifier.OUT)
1618 // Dont allocate till we find an out var.
1620 map = new VariableInfo [Count];
1622 map [i] = new VariableInfo (ip.ParameterName (i),
1623 TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
1625 Length += map [i].Length;
1629 public VariableMap (LocalInfo[] locals)
1630 : this (null, locals)
1633 public VariableMap (VariableMap parent, LocalInfo[] locals)
1635 int offset = 0, start = 0;
1636 if (parent != null && parent.map != null) {
1637 offset = parent.Length;
1638 start = parent.Count;
1641 Count = locals.Length + start;
1646 map = new VariableInfo [Count];
1649 if (parent != null && parent.map != null) {
1650 parent.map.CopyTo (map, 0);
1653 for (int i = start; i < Count; i++) {
1654 LocalInfo li = locals [i-start];
1656 if (li.VariableType == null)
1659 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1660 Length += map [i].Length;
1665 // Returns the VariableInfo for variable @index or null if we don't need to
1666 // compute assignment info for this variable.
1668 public VariableInfo this [int index] {
1677 public override string ToString ()
1679 return String.Format ("VariableMap ({0}:{1})", Count, Length);
1684 // This is a special bit vector which can inherit from another bit vector doing a
1685 // copy-on-write strategy. The inherited vector may have a smaller size than the
1688 public class MyBitVector {
1689 public readonly int Count;
1690 public static readonly MyBitVector Empty = new MyBitVector ();
1692 // Invariant: vector != null => vector.Count == Count
1693 // Invariant: vector == null || shared == null
1694 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1695 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1696 BitArray vector, shared;
1700 shared = new BitArray (0, false);
1703 public MyBitVector (MyBitVector InheritsFrom, int Count)
1705 if (InheritsFrom != null)
1706 shared = InheritsFrom.Shared;
1711 // Use this accessor to get a shareable copy of the underlying BitArray representation
1714 // Post-condition: vector == null
1715 if (shared == null) {
1724 // Get/set bit `index' in the bit vector.
1726 public bool this [int index] {
1729 throw new ArgumentOutOfRangeException ();
1732 return vector [index];
1735 if (index < shared.Count)
1736 return shared [index];
1741 // Only copy the vector if we're actually modifying it.
1742 if (this [index] != value) {
1744 initialize_vector ();
1745 vector [index] = value;
1751 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1752 // different size than the current one.
1754 private MyBitVector Or (MyBitVector new_vector)
1756 if (Count == 0 || new_vector.Count == 0)
1759 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1762 int n = new_vector.Count;
1764 for (int i = 0; i < n; ++i)
1772 if (Count == o.Count) {
1773 if (vector == null) {
1776 initialize_vector ();
1786 for (int i = 0; i < min; i++) {
1795 // Performs an `and' operation on the bit vector. The `new_vector' may have
1796 // a different size than the current one.
1798 private MyBitVector And (MyBitVector new_vector)
1803 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1806 for (int i = new_vector.Count; i < Count; ++i)
1816 if (Count == o.Count) {
1817 if (vector == null) {
1818 if (shared == null) {
1819 shared = new_vector.Shared;
1822 initialize_vector ();
1832 for (int i = 0; i < min; i++) {
1837 for (int i = min; i < Count; i++)
1843 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1851 if (a.Count > b.Count)
1852 return a.Clone ().And (b);
1854 return b.Clone ().And (a);
1857 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1862 return new MyBitVector (null, b.Count);
1864 return new MyBitVector (null, a.Count);
1865 if (a.Count > b.Count)
1866 return a.Clone ().Or (b);
1868 return b.Clone ().Or (a);
1871 public MyBitVector Clone ()
1873 return Count == 0 ? Empty : new MyBitVector (this, Count);
1876 public void SetAll (bool value)
1878 // Don't clobber Empty
1881 shared = value ? null : Empty.Shared;
1885 void initialize_vector ()
1887 // Post-condition: vector != null
1888 if (shared == null) {
1889 vector = new BitArray (Count, true);
1893 vector = new BitArray (shared);
1894 if (Count != vector.Count)
1895 vector.Length = Count;
1899 StringBuilder Dump (StringBuilder sb)
1901 BitArray dump = vector == null ? shared : vector;
1903 return sb.Append ("/");
1906 for (int i = 0; i < dump.Count; i++)
1907 sb.Append (dump [i] ? "1" : "0");
1911 public override string ToString ()
1913 return Dump (new StringBuilder ("{")).Append ("}").ToString ();