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
62 // The type of one sibling of a branching.
64 public enum SiblingType : byte {
73 public sealed class Reachability
75 TriState returns, throws, barrier;
77 public TriState Returns {
78 get { return returns; }
80 public TriState Throws {
81 get { return throws; }
83 public TriState Barrier {
84 get { return barrier; }
87 Reachability (TriState returns, TriState throws, TriState barrier)
89 this.returns = returns;
91 this.barrier = barrier;
94 public Reachability Clone ()
96 return new Reachability (returns, throws, 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 throws = TriState_Meet (throws, b.throws);
121 barrier = TriState_Meet (barrier, b.barrier);
124 public void Or (Reachability b)
126 returns = TriState_Max (returns, b.returns);
127 throws = TriState_Max (throws, b.throws);
128 barrier = TriState_Max (barrier, b.barrier);
131 public static Reachability Always ()
133 return new Reachability (TriState.Never, TriState.Never, TriState.Never);
136 TriState Unreachable {
137 get { return TriState_Max (returns, TriState_Max (throws, barrier)); }
142 TriState unreachable = Unreachable;
143 if (unreachable == TriState.Sometimes)
144 return TriState.Sometimes;
145 return unreachable == TriState.Always ? TriState.Never : TriState.Always;
149 public bool AlwaysReturns {
150 get { return returns == TriState.Always; }
153 public bool AlwaysThrows {
154 get { return throws == TriState.Always; }
157 public bool AlwaysHasBarrier {
158 get { return barrier == TriState.Always; }
161 public bool IsUnreachable {
162 get { return Unreachable == TriState.Always; }
165 public void SetReturns ()
167 returns = TriState.Always;
170 public void SetThrows ()
172 throws = TriState.Always;
175 public void SetBarrier ()
177 barrier = TriState.Always;
180 static string ShortName (TriState returns)
185 case TriState.Sometimes:
192 public override string ToString ()
194 return String.Format ("[{0}:{1}:{2}:{3}]",
195 ShortName (returns), ShortName (throws), ShortName (barrier),
196 ShortName (Reachable));
200 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
203 case BranchingType.Exception:
204 case BranchingType.Labeled:
205 throw new InvalidOperationException ();
207 case BranchingType.Switch:
208 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
210 case BranchingType.SwitchSection:
211 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
213 case BranchingType.Block:
214 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
216 case BranchingType.Loop:
217 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
219 case BranchingType.Embedded:
220 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
223 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
228 // The type of this flow branching.
230 public readonly BranchingType Type;
233 // The block this branching is contained in. This may be null if it's not
234 // a top-level block and it doesn't declare any local variables.
236 public readonly Block Block;
239 // The parent of this branching or null if this is the top-block.
241 public readonly FlowBranching Parent;
244 // Start-Location of this flow branching.
246 public readonly Location Location;
251 VariableMap param_map, local_map;
253 static int next_id = 0;
257 // The vector contains a BitArray with information about which local variables
258 // and parameters are already initialized at the current code position.
260 public class UsageVector {
262 // The type of this branching.
264 public readonly SiblingType Type;
267 // Start location of this branching.
269 public Location Location;
272 // This is only valid for SwitchSection, Try, Catch and Finally.
274 public readonly Block Block;
277 // If this is true, then the usage vector has been modified and must be
278 // merged when we're done with this branching.
283 // The number of parameters in this block.
285 public readonly int CountParameters;
288 // The number of locals in this block.
290 public readonly int CountLocals;
293 // If not null, then we inherit our state from this vector and do a
294 // copy-on-write. If null, then we're the first sibling in a top-level
295 // block and inherit from the empty vector.
297 public readonly UsageVector InheritsFrom;
300 // This is used to construct a list of UsageVector's.
302 public UsageVector Next;
307 MyBitVector locals, parameters;
308 Reachability reachability;
310 static int next_id = 0;
314 // Normally, you should not use any of these constructors.
316 public UsageVector (SiblingType type, UsageVector parent,
317 Block block, Location loc,
318 int num_params, int num_locals)
323 this.InheritsFrom = parent;
324 this.CountParameters = num_params;
325 this.CountLocals = num_locals;
327 if (parent != null) {
329 locals = new MyBitVector (parent.locals, CountLocals);
332 parameters = new MyBitVector (parent.parameters, num_params);
334 reachability = parent.Reachability.Clone ();
337 locals = new MyBitVector (null, CountLocals);
340 parameters = new MyBitVector (null, num_params);
342 reachability = Reachability.Always ();
348 public UsageVector (SiblingType type, UsageVector parent,
349 Block block, Location loc)
350 : this (type, parent, block, loc,
351 parent.CountParameters, parent.CountLocals)
354 public UsageVector (MyBitVector parameters, MyBitVector locals,
355 Reachability reachability, Block block,
358 this.Type = SiblingType.Block;
362 this.reachability = reachability;
363 this.parameters = parameters;
364 this.locals = locals;
370 // This does a deep copy of the usage vector.
372 public UsageVector Clone ()
374 UsageVector retval = new UsageVector (
375 Type, null, Block, Location,
376 CountParameters, CountLocals);
378 if (retval.locals != null)
379 retval.locals = locals.Clone ();
381 if (parameters != null)
382 retval.parameters = parameters.Clone ();
384 retval.reachability = reachability.Clone ();
389 public bool IsAssigned (VariableInfo var, bool ignoreReachability)
391 if (!ignoreReachability && !var.IsParameter && Reachability.IsUnreachable)
394 return var.IsAssigned (var.IsParameter ? parameters : locals);
397 public void SetAssigned (VariableInfo var)
399 if (!var.IsParameter && Reachability.IsUnreachable)
403 var.SetAssigned (var.IsParameter ? parameters : locals);
406 public bool IsFieldAssigned (VariableInfo var, string name)
408 if (!var.IsParameter && Reachability.IsUnreachable)
411 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
414 public void SetFieldAssigned (VariableInfo var, string name)
416 if (!var.IsParameter && Reachability.IsUnreachable)
420 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
423 public Reachability Reachability {
424 get { return reachability; }
427 public void Return ()
429 if (!reachability.IsUnreachable) {
431 reachability.SetReturns ();
437 if (!reachability.IsUnreachable) {
439 reachability.SetThrows ();
440 reachability.SetBarrier ();
446 if (!reachability.IsUnreachable) {
448 reachability.SetBarrier ();
453 // Merges a child branching.
455 public UsageVector MergeChild (UsageVector child, bool implicit_block)
457 Report.Debug (2, " MERGING CHILD EFFECTS", this, child, IsDirty, reachability, Type);
459 Reachability new_r = child.Reachability;
462 // We've now either reached the point after the branching or we will
463 // never get there since we always return or always throw an exception.
465 // If we can reach the point after the branching, mark all locals and
466 // parameters as initialized which have been initialized in all branches
467 // we need to look at (see above).
470 if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
471 Report.Error (163, Location,
472 "Control cannot fall through from one " +
473 "case label to another");
477 if (locals != null && child.LocalVector != null)
478 locals.Or (child.LocalVector);
480 if (child.ParameterVector != null)
481 parameters.Or (child.ParameterVector);
484 reachability = new_r.Clone ();
486 reachability.Or (new_r);
494 // Tells control flow analysis that the current code position may be reached with
495 // a forward jump from any of the origins listed in `origin_vectors' which is a
496 // list of UsageVectors.
498 // This is used when resolving forward gotos - in the following example, the
499 // variable `a' is uninitialized in line 8 becase this line may be reached via
500 // the goto in line 4:
510 // 8 Console.WriteLine (a);
513 public void MergeJumpOrigins (UsageVector o_vectors)
515 Report.Debug (1, " MERGING JUMP ORIGINS", this);
517 reachability = Reachability.Always ();
519 if (o_vectors == null) {
520 reachability.SetBarrier ();
526 for (UsageVector vector = o_vectors; vector != null;
527 vector = vector.Next) {
528 Report.Debug (1, " MERGING JUMP ORIGIN", vector,
529 first, locals, vector.Locals);
532 if (locals != null && vector.Locals != null)
533 locals.Or (vector.locals);
535 if (parameters != null)
536 parameters.Or (vector.parameters);
540 locals.And (vector.locals);
541 if (parameters != null)
542 parameters.And (vector.parameters);
545 reachability.Meet (vector.Reachability);
547 Report.Debug (1, " MERGING JUMP ORIGIN #1", vector);
550 Report.Debug (1, " MERGING JUMP ORIGINS DONE", this);
553 public void MergeOrigins (UsageVector o_vectors)
555 Report.Debug (1, " MERGING BREAK ORIGINS", this);
557 if (o_vectors == null)
560 bool first = reachability.IsUnreachable;
562 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
563 Report.Debug (1, " MERGING BREAK ORIGIN", vector, first);
566 locals = vector.Locals;
567 parameters = vector.Parameters;
570 if (locals != null && vector.locals != null)
571 locals.And (vector.locals);
572 if (parameters != null && vector.parameters != null)
573 parameters.And (vector.parameters);
576 reachability.Meet (vector.Reachability);
579 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
583 // Performs an `or' operation on the locals and the parameters.
585 public void Or (UsageVector new_vector)
588 locals.Or (new_vector.locals);
589 if (parameters != null)
590 parameters.Or (new_vector.parameters);
594 // Performs an `and' operation on the locals.
596 public void AndLocals (UsageVector new_vector)
599 locals.And (new_vector.locals);
602 public bool HasParameters {
603 get { return parameters != null; }
606 public bool HasLocals {
607 get { return locals != null; }
611 // Returns a deep copy of the parameters.
613 public MyBitVector Parameters {
614 get { return parameters == null ? null : parameters.Clone (); }
618 // Returns a deep copy of the locals.
620 public MyBitVector Locals {
621 get { return locals == null ? null : locals.Clone (); }
624 public MyBitVector ParameterVector {
625 get { return parameters; }
628 public MyBitVector LocalVector {
629 get { return locals; }
636 public override string ToString ()
638 StringBuilder sb = new StringBuilder ();
640 sb.Append ("Vector (");
647 sb.Append (reachability);
648 if (parameters != null) {
650 sb.Append (parameters);
656 return sb.ToString ();
661 // Creates a new flow branching which is contained in `parent'.
662 // You should only pass non-null for the `block' argument if this block
663 // introduces any new variables - in this case, we need to create a new
664 // usage vector with a different size than our parent's one.
666 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
667 Block block, Location loc)
677 param_map = Block.ParameterMap;
678 local_map = Block.LocalMap;
680 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
681 vector = new UsageVector (
682 stype, parent_vector, Block, loc,
683 param_map.Length, local_map.Length);
685 param_map = Parent.param_map;
686 local_map = Parent.local_map;
687 vector = new UsageVector (
688 stype, Parent.CurrentUsageVector, null, loc);
694 public abstract UsageVector CurrentUsageVector {
699 // Creates a sibling of the current usage vector.
701 public virtual void CreateSibling (Block block, SiblingType type)
703 UsageVector vector = new UsageVector (
704 type, Parent.CurrentUsageVector, block, Location);
707 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
710 public void CreateSibling ()
712 CreateSibling (null, SiblingType.Conditional);
715 protected abstract void AddSibling (UsageVector uv);
717 public virtual LabeledStatement LookupLabel (string name, Location loc)
720 return Parent.LookupLabel (name, loc);
724 "No such label `" + name + "' in this scope");
728 public abstract void Label (UsageVector origin_vectors);
731 // Check whether all `out' parameters have been assigned.
733 public void CheckOutParameters (MyBitVector parameters, Location loc)
735 if (parameters == null)
738 for (int i = 0; i < param_map.Count; i++) {
739 VariableInfo var = param_map [i];
744 if (var.IsAssigned (parameters))
747 Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
752 protected UsageVector Merge (UsageVector sibling_list)
754 if (sibling_list.Next == null)
757 MyBitVector locals = null;
758 MyBitVector parameters = null;
760 Reachability reachability = null;
762 Report.Debug (2, " MERGING SIBLINGS", this, Name);
764 for (UsageVector child = sibling_list; child != null; child = child.Next) {
765 Report.Debug (2, " MERGING SIBLING ", reachability, child);
767 if (reachability == null)
768 reachability = child.Reachability.Clone ();
770 reachability.Meet (child.Reachability);
772 // A local variable is initialized after a flow branching if it
773 // has been initialized in all its branches which do neither
774 // always return or always throw an exception.
776 // If a branch may return, but does not always return, then we
777 // can treat it like a never-returning branch here: control will
778 // only reach the code position after the branching if we did not
781 // It's important to distinguish between always and sometimes
782 // returning branches here:
785 // 2 if (something) {
789 // 6 Console.WriteLine (a);
791 // The if block in lines 3-4 always returns, so we must not look
792 // at the initialization of `a' in line 4 - thus it'll still be
793 // uninitialized in line 6.
795 // On the other hand, the following is allowed:
802 // 6 Console.WriteLine (a);
804 // Here, `a' is initialized in line 3 and we must not look at
805 // line 5 since it always returns.
807 bool unreachable = child.Reachability.IsUnreachable;
809 Report.Debug (2, " MERGING SIBLING #1", reachability,
810 Type, child.Type, child.Reachability.IsUnreachable, unreachable);
812 if (!unreachable && (child.LocalVector != null))
813 MyBitVector.And (ref locals, child.LocalVector);
815 // An `out' parameter must be assigned in all branches which do
816 // not always throw an exception.
817 if ((child.ParameterVector != null) && !child.Reachability.AlwaysThrows)
818 MyBitVector.And (ref parameters, child.ParameterVector);
820 Report.Debug (2, " MERGING SIBLING #2", parameters, locals);
823 if (reachability == null)
824 throw new InternalErrorException ("Cannot happen: the loop above runs at least twice");
826 Report.Debug (2, " MERGING SIBLINGS DONE", parameters, locals, reachability);
828 return new UsageVector (parameters, locals, reachability, null, Location);
831 protected abstract UsageVector Merge ();
834 // Merge a child branching.
836 public UsageVector MergeChild (FlowBranching child)
838 bool implicit_block = child.Type == BranchingType.Block && child.Block.Implicit;
839 Report.Debug (2, " MERGING CHILD", this, child);
840 UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), implicit_block);
841 Report.Debug (2, " MERGING CHILD DONE", this, result);
846 // Does the toplevel merging.
848 public Reachability MergeTopBlock ()
850 if ((Type != BranchingType.Block) || (Block == null))
851 throw new NotSupportedException ();
853 UsageVector result = Merge ();
855 Report.Debug (4, "MERGE TOP BLOCK", Location, result);
857 if (!result.Reachability.AlwaysThrows && !result.Reachability.AlwaysHasBarrier)
858 CheckOutParameters (result.Parameters, Location);
860 return result.Reachability;
863 public virtual bool InTryWithCatch ()
865 return Parent != null && Parent.InTryWithCatch ();
868 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
869 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
872 return Parent.AddBreakOrigin (vector, loc);
874 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
878 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
879 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
882 return Parent.AddContinueOrigin (vector, loc);
884 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
888 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
889 public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
892 return Parent.AddReturnOrigin (vector, loc);
894 CheckOutParameters (vector.Parameters, loc);
898 public virtual void StealFinallyClauses (ref ArrayList list)
901 Parent.StealFinallyClauses (ref list);
904 public bool IsAssigned (VariableInfo vi)
906 return CurrentUsageVector.IsAssigned (vi, false);
909 public bool IsFieldAssigned (VariableInfo vi, string field_name)
911 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
914 public void SetAssigned (VariableInfo vi)
916 CurrentUsageVector.SetAssigned (vi);
919 public void SetFieldAssigned (VariableInfo vi, string name)
921 CurrentUsageVector.SetFieldAssigned (vi, name);
924 public override string ToString ()
926 StringBuilder sb = new StringBuilder ();
927 sb.Append (GetType ());
935 sb.Append (Block.ID);
937 sb.Append (Block.StartLocation);
940 // sb.Append (Siblings.Length);
941 // sb.Append (" - ");
942 sb.Append (CurrentUsageVector);
944 return sb.ToString ();
948 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
952 public class FlowBranchingBlock : FlowBranching
954 UsageVector sibling_list = null;
956 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
957 SiblingType stype, Block block, Location loc)
958 : base (parent, type, stype, block, loc)
961 public override UsageVector CurrentUsageVector {
962 get { return sibling_list; }
965 protected override void AddSibling (UsageVector sibling)
967 sibling.Next = sibling_list;
968 sibling_list = sibling;
971 public override LabeledStatement LookupLabel (string name, Location loc)
974 return base.LookupLabel (name, loc);
976 LabeledStatement s = Block.LookupLabel (name);
980 return base.LookupLabel (name, loc);
983 public override void Label (UsageVector origin_vectors)
985 if (!CurrentUsageVector.Reachability.IsUnreachable) {
986 UsageVector vector = CurrentUsageVector.Clone ();
987 vector.Next = origin_vectors;
988 origin_vectors = vector;
991 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
994 protected override UsageVector Merge ()
996 return Merge (sibling_list);
1000 public class FlowBranchingBreakable : FlowBranchingBlock
1002 UsageVector break_origins;
1004 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
1005 : base (parent, type, stype, block, loc)
1008 public override bool AddBreakOrigin (UsageVector vector, Location loc)
1010 vector = vector.Clone ();
1011 vector.Next = break_origins;
1012 break_origins = vector;
1016 protected override UsageVector Merge ()
1018 UsageVector vector = base.Merge ();
1019 vector.MergeOrigins (break_origins);
1024 public class FlowBranchingContinuable : FlowBranchingBlock
1026 UsageVector continue_origins;
1028 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
1029 : base (parent, type, stype, block, loc)
1032 public override bool AddContinueOrigin (UsageVector vector, Location loc)
1034 vector = vector.Clone ();
1035 vector.Next = continue_origins;
1036 continue_origins = vector;
1040 protected override UsageVector Merge ()
1042 UsageVector vector = base.Merge ();
1043 vector.MergeOrigins (continue_origins);
1048 public class FlowBranchingLabeled : FlowBranchingBlock
1050 LabeledStatement stmt;
1051 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
1052 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
1058 public class FlowBranchingException : FlowBranching
1060 ExceptionStatement stmt;
1061 UsageVector current_vector;
1062 UsageVector catch_vectors;
1063 UsageVector finally_vector;
1065 UsageVector break_origins;
1066 UsageVector continue_origins;
1067 UsageVector return_origins;
1071 public FlowBranchingException (FlowBranching parent,
1072 ExceptionStatement stmt)
1073 : base (parent, BranchingType.Exception, SiblingType.Try,
1077 this.emit_finally = true;
1080 protected override void AddSibling (UsageVector sibling)
1082 switch (sibling.Type) {
1083 case SiblingType.Try:
1084 case SiblingType.Catch:
1085 sibling.Next = catch_vectors;
1086 catch_vectors = sibling;
1088 case SiblingType.Finally:
1089 finally_vector = sibling;
1092 throw new InvalidOperationException ();
1094 current_vector = sibling;
1097 public override UsageVector CurrentUsageVector {
1098 get { return current_vector; }
1101 public override bool InTryWithCatch ()
1103 if (finally_vector == null) {
1104 Try t = stmt as Try;
1105 if (t != null && t.HasCatch)
1109 return base.InTryWithCatch ();
1112 public override bool AddBreakOrigin (UsageVector vector, Location loc)
1114 if (finally_vector != null) {
1115 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1117 vector = vector.Clone ();
1118 vector.Location = loc;
1119 vector.Next = break_origins;
1120 break_origins = vector;
1125 public override bool AddContinueOrigin (UsageVector vector, Location loc)
1127 if (finally_vector != null) {
1128 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1130 vector = vector.Clone ();
1131 vector.Location = loc;
1132 vector.Next = continue_origins;
1133 continue_origins = vector;
1138 public override bool AddReturnOrigin (UsageVector vector, Location loc)
1140 if (finally_vector != null) {
1141 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1143 vector = vector.Clone ();
1144 vector.Location = loc;
1145 vector.Next = return_origins;
1146 return_origins = vector;
1151 public override void StealFinallyClauses (ref ArrayList list)
1154 list = new ArrayList ();
1156 emit_finally = false;
1157 base.StealFinallyClauses (ref list);
1160 public bool EmitFinally {
1161 get { return emit_finally; }
1164 public override LabeledStatement LookupLabel (string name, Location loc)
1166 if (current_vector.Block == null)
1167 return base.LookupLabel (name, loc);
1169 LabeledStatement s = current_vector.Block.LookupLabel (name);
1173 if (finally_vector != null) {
1174 Report.Error (157, loc,
1175 "Control cannot leave the body of a finally clause");
1179 return base.LookupLabel (name, loc);
1182 public override void Label (UsageVector origin_vectors)
1184 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1187 protected override UsageVector Merge ()
1189 UsageVector vector = Merge (catch_vectors);
1191 if (finally_vector != null)
1192 vector.MergeChild (finally_vector, false);
1194 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
1195 if (finally_vector != null)
1196 origin.MergeChild (finally_vector, false);
1197 if (!origin.Reachability.IsUnreachable)
1198 Parent.AddBreakOrigin (origin, origin.Location);
1201 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
1202 if (finally_vector != null)
1203 origin.MergeChild (finally_vector, false);
1204 if (!origin.Reachability.IsUnreachable)
1205 Parent.AddContinueOrigin (origin, origin.Location);
1208 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
1209 if (finally_vector != null)
1210 origin.MergeChild (finally_vector, false);
1211 if (!origin.Reachability.IsUnreachable)
1212 Parent.AddReturnOrigin (origin, origin.Location);
1220 // This is used by the flow analysis code to keep track of the type of local variables
1223 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1224 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1225 // you can only assign the whole variable as such.
1227 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1228 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1229 // one bit for each of its fields.
1231 // This class computes this `layout' for each type.
1233 public class TypeInfo
1235 public readonly Type Type;
1238 // Total number of bits a variable of this type consumes in the flow vector.
1240 public readonly int TotalLength;
1243 // Number of bits the simple fields of a variable of this type consume
1244 // in the flow vector.
1246 public readonly int Length;
1249 // This is only used by sub-structs.
1251 public readonly int Offset;
1254 // If this is a struct.
1256 public readonly bool IsStruct;
1259 // If this is a struct, all fields which are structs theirselves.
1261 public TypeInfo[] SubStructInfo;
1263 protected readonly StructInfo struct_info;
1264 private static Hashtable type_hash = new Hashtable ();
1266 public static TypeInfo GetTypeInfo (Type type)
1268 TypeInfo info = (TypeInfo) type_hash [type];
1272 info = new TypeInfo (type);
1273 type_hash.Add (type, info);
1277 public static TypeInfo GetTypeInfo (TypeContainer tc)
1279 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1283 info = new TypeInfo (tc);
1284 type_hash.Add (tc.TypeBuilder, info);
1288 private TypeInfo (Type type)
1292 struct_info = StructInfo.GetStructInfo (type);
1293 if (struct_info != null) {
1294 Length = struct_info.Length;
1295 TotalLength = struct_info.TotalLength;
1296 SubStructInfo = struct_info.StructFields;
1305 private TypeInfo (TypeContainer tc)
1307 this.Type = tc.TypeBuilder;
1309 struct_info = StructInfo.GetStructInfo (tc);
1310 if (struct_info != null) {
1311 Length = struct_info.Length;
1312 TotalLength = struct_info.TotalLength;
1313 SubStructInfo = struct_info.StructFields;
1322 protected TypeInfo (StructInfo struct_info, int offset)
1324 this.struct_info = struct_info;
1325 this.Offset = offset;
1326 this.Length = struct_info.Length;
1327 this.TotalLength = struct_info.TotalLength;
1328 this.SubStructInfo = struct_info.StructFields;
1329 this.Type = struct_info.Type;
1330 this.IsStruct = true;
1333 public int GetFieldIndex (string name)
1335 if (struct_info == null)
1338 return struct_info [name];
1341 public TypeInfo GetSubStruct (string name)
1343 if (struct_info == null)
1346 return struct_info.GetStructField (name);
1350 // A struct's constructor must always assign all fields.
1351 // This method checks whether it actually does so.
1353 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1355 if (struct_info == null)
1359 for (int i = 0; i < struct_info.Count; i++) {
1360 FieldInfo field = struct_info.Fields [i];
1362 if (!branching.IsFieldAssigned (vi, field.Name)) {
1363 Report.Error (171, loc,
1364 "Field `{0}' must be fully assigned before control leaves the constructor",
1365 TypeManager.GetFullNameSignature (field));
1373 public override string ToString ()
1375 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1376 Type, Offset, Length, TotalLength);
1379 protected class StructInfo {
1380 public readonly Type Type;
1381 public readonly FieldInfo[] Fields;
1382 public readonly TypeInfo[] StructFields;
1383 public readonly int Count;
1384 public readonly int CountPublic;
1385 public readonly int CountNonPublic;
1386 public readonly int Length;
1387 public readonly int TotalLength;
1388 public readonly bool HasStructFields;
1390 private static Hashtable field_type_hash = new Hashtable ();
1391 private Hashtable struct_field_hash;
1392 private Hashtable field_hash;
1394 protected bool InTransit = false;
1396 // Private constructor. To save memory usage, we only need to create one instance
1397 // of this class per struct type.
1398 private StructInfo (Type type)
1402 field_type_hash.Add (type, this);
1404 if (type is TypeBuilder) {
1405 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1407 ArrayList fields = null;
1411 ArrayList public_fields = new ArrayList ();
1412 ArrayList non_public_fields = new ArrayList ();
1414 if (fields != null) {
1415 foreach (FieldMember field in fields) {
1416 if ((field.ModFlags & Modifiers.STATIC) != 0)
1418 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1419 public_fields.Add (field.FieldBuilder);
1421 non_public_fields.Add (field.FieldBuilder);
1425 CountPublic = public_fields.Count;
1426 CountNonPublic = non_public_fields.Count;
1427 Count = CountPublic + CountNonPublic;
1429 Fields = new FieldInfo [Count];
1430 public_fields.CopyTo (Fields, 0);
1431 non_public_fields.CopyTo (Fields, CountPublic);
1433 FieldInfo[] public_fields = type.GetFields (
1434 BindingFlags.Instance|BindingFlags.Public);
1435 FieldInfo[] non_public_fields = type.GetFields (
1436 BindingFlags.Instance|BindingFlags.NonPublic);
1438 CountPublic = public_fields.Length;
1439 CountNonPublic = non_public_fields.Length;
1440 Count = CountPublic + CountNonPublic;
1442 Fields = new FieldInfo [Count];
1443 public_fields.CopyTo (Fields, 0);
1444 non_public_fields.CopyTo (Fields, CountPublic);
1447 struct_field_hash = new Hashtable ();
1448 field_hash = new Hashtable ();
1451 StructFields = new TypeInfo [Count];
1452 StructInfo[] sinfo = new StructInfo [Count];
1456 for (int i = 0; i < Count; i++) {
1457 FieldInfo field = (FieldInfo) Fields [i];
1459 sinfo [i] = GetStructInfo (field.FieldType);
1460 if (sinfo [i] == null)
1461 field_hash.Add (field.Name, ++Length);
1462 else if (sinfo [i].InTransit) {
1463 Report.Error (523, String.Format (
1464 "Struct member `{0}.{1}' of type `{2}' causes " +
1465 "a cycle in the structure layout",
1466 type, field.Name, sinfo [i].Type));
1474 TotalLength = Length + 1;
1475 for (int i = 0; i < Count; i++) {
1476 FieldInfo field = (FieldInfo) Fields [i];
1478 if (sinfo [i] == null)
1481 field_hash.Add (field.Name, TotalLength);
1483 HasStructFields = true;
1484 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1485 struct_field_hash.Add (field.Name, StructFields [i]);
1486 TotalLength += sinfo [i].TotalLength;
1490 public int this [string name] {
1492 if (field_hash.Contains (name))
1493 return (int) field_hash [name];
1499 public TypeInfo GetStructField (string name)
1501 return (TypeInfo) struct_field_hash [name];
1504 public static StructInfo GetStructInfo (Type type)
1506 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1507 TypeManager.IsBuiltinType (type))
1510 StructInfo info = (StructInfo) field_type_hash [type];
1514 return new StructInfo (type);
1517 public static StructInfo GetStructInfo (TypeContainer tc)
1519 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1523 return new StructInfo (tc.TypeBuilder);
1529 // This is used by the flow analysis code to store information about a single local variable
1530 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1531 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1532 // it has been assigned or not, but for structs, we need this information for each of its fields.
1534 public class VariableInfo {
1535 public readonly string Name;
1536 public readonly TypeInfo TypeInfo;
1539 // The bit offset of this variable in the flow vector.
1541 public readonly int Offset;
1544 // The number of bits this variable needs in the flow vector.
1545 // The first bit always specifies whether the variable as such has been assigned while
1546 // the remaining bits contain this information for each of a struct's fields.
1548 public readonly int Length;
1551 // If this is a parameter of local variable.
1553 public readonly bool IsParameter;
1555 public readonly LocalInfo LocalInfo;
1556 public readonly int ParameterIndex;
1558 readonly VariableInfo Parent;
1559 VariableInfo[] sub_info;
1561 protected VariableInfo (string name, Type type, int offset)
1564 this.Offset = offset;
1565 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1567 Length = TypeInfo.TotalLength;
1572 protected VariableInfo (VariableInfo parent, TypeInfo type)
1574 this.Name = parent.Name;
1575 this.TypeInfo = type;
1576 this.Offset = parent.Offset + type.Offset;
1577 this.Parent = parent;
1578 this.Length = type.TotalLength;
1580 this.IsParameter = parent.IsParameter;
1581 this.LocalInfo = parent.LocalInfo;
1582 this.ParameterIndex = parent.ParameterIndex;
1587 protected void Initialize ()
1589 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1590 if (sub_fields != null) {
1591 sub_info = new VariableInfo [sub_fields.Length];
1592 for (int i = 0; i < sub_fields.Length; i++) {
1593 if (sub_fields [i] != null)
1594 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1597 sub_info = new VariableInfo [0];
1600 public VariableInfo (LocalInfo local_info, int offset)
1601 : this (local_info.Name, local_info.VariableType, offset)
1603 this.LocalInfo = local_info;
1604 this.IsParameter = false;
1607 public VariableInfo (string name, Type type, int param_idx, int offset)
1608 : this (name, type, offset)
1610 this.ParameterIndex = param_idx;
1611 this.IsParameter = true;
1614 public bool IsAssigned (EmitContext ec)
1616 return !ec.DoFlowAnalysis ||
1617 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1618 ec.CurrentBranching.IsAssigned (this);
1621 public bool IsAssigned (EmitContext ec, Location loc)
1623 if (IsAssigned (ec))
1626 Report.Error (165, loc,
1627 "Use of unassigned local variable `" + Name + "'");
1628 ec.CurrentBranching.SetAssigned (this);
1632 public bool IsAssigned (MyBitVector vector)
1634 if (vector [Offset])
1637 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1638 if (vector [parent.Offset])
1641 // Return unless this is a struct.
1642 if (!TypeInfo.IsStruct)
1645 // Ok, so each field must be assigned.
1646 for (int i = 0; i < TypeInfo.Length; i++) {
1647 if (!vector [Offset + i + 1])
1651 // Ok, now check all fields which are structs.
1652 for (int i = 0; i < sub_info.Length; i++) {
1653 VariableInfo sinfo = sub_info [i];
1657 if (!sinfo.IsAssigned (vector))
1661 vector [Offset] = true;
1665 public void SetAssigned (EmitContext ec)
1667 if (ec.DoFlowAnalysis)
1668 ec.CurrentBranching.SetAssigned (this);
1671 public void SetAssigned (MyBitVector vector)
1673 vector [Offset] = true;
1676 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1678 if (!ec.DoFlowAnalysis ||
1679 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1680 ec.CurrentBranching.IsFieldAssigned (this, name))
1683 Report.Error (170, loc,
1684 "Use of possibly unassigned field `" + name + "'");
1685 ec.CurrentBranching.SetFieldAssigned (this, name);
1689 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1691 int field_idx = TypeInfo.GetFieldIndex (field_name);
1696 return vector [Offset + field_idx];
1699 public void SetFieldAssigned (EmitContext ec, string name)
1701 if (ec.DoFlowAnalysis)
1702 ec.CurrentBranching.SetFieldAssigned (this, name);
1705 public void SetFieldAssigned (MyBitVector vector, string field_name)
1707 int field_idx = TypeInfo.GetFieldIndex (field_name);
1712 vector [Offset + field_idx] = true;
1715 public VariableInfo GetSubStruct (string name)
1717 TypeInfo type = TypeInfo.GetSubStruct (name);
1722 return new VariableInfo (this, type);
1725 public override string ToString ()
1727 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1728 Name, TypeInfo, Offset, Length, IsParameter);
1733 // This is used by the flow code to hold the `layout' of the flow vector for
1734 // all locals and all parameters (ie. we create one instance of this class for the
1735 // locals and another one for the params).
1737 public class VariableMap {
1739 // The number of variables in the map.
1741 public readonly int Count;
1744 // Total length of the flow vector for this map.
1746 public readonly int Length;
1750 public VariableMap (Parameters ip)
1752 Count = ip != null ? ip.Count : 0;
1754 // Dont bother allocating anything!
1760 for (int i = 0; i < Count; i++) {
1761 Parameter.Modifier mod = ip.ParameterModifier (i);
1763 if ((mod & Parameter.Modifier.OUT) != Parameter.Modifier.OUT)
1766 // Dont allocate till we find an out var.
1768 map = new VariableInfo [Count];
1770 map [i] = new VariableInfo (ip.ParameterName (i),
1771 TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
1773 Length += map [i].Length;
1777 public VariableMap (LocalInfo[] locals)
1778 : this (null, locals)
1781 public VariableMap (VariableMap parent, LocalInfo[] locals)
1783 int offset = 0, start = 0;
1784 if (parent != null && parent.map != null) {
1785 offset = parent.Length;
1786 start = parent.Count;
1789 Count = locals.Length + start;
1794 map = new VariableInfo [Count];
1797 if (parent != null && parent.map != null) {
1798 parent.map.CopyTo (map, 0);
1801 for (int i = start; i < Count; i++) {
1802 LocalInfo li = locals [i-start];
1804 if (li.VariableType == null)
1807 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1808 Length += map [i].Length;
1813 // Returns the VariableInfo for variable @index or null if we don't need to
1814 // compute assignment info for this variable.
1816 public VariableInfo this [int index] {
1825 public override string ToString ()
1827 return String.Format ("VariableMap ({0}:{1})", Count, Length);
1832 // This is a special bit vector which can inherit from another bit vector doing a
1833 // copy-on-write strategy. The inherited vector may have a smaller size than the
1836 public class MyBitVector {
1837 public readonly int Count;
1838 public readonly MyBitVector InheritsFrom;
1843 public MyBitVector (int Count)
1844 : this (null, Count)
1847 public MyBitVector (MyBitVector InheritsFrom, int Count)
1849 this.InheritsFrom = InheritsFrom;
1854 // Checks whether this bit vector has been modified. After setting this to true,
1855 // we won't use the inherited vector anymore, but our own copy of it.
1857 public bool IsDirty {
1858 get { return is_dirty; }
1862 initialize_vector ();
1867 // Get/set bit `index' in the bit vector.
1869 public bool this [int index]
1873 throw new ArgumentOutOfRangeException ();
1875 // We're doing a "copy-on-write" strategy here; as long
1876 // as nobody writes to the array, we can use our parent's
1877 // copy instead of duplicating the vector.
1880 return vector [index];
1881 else if (InheritsFrom != null) {
1882 BitArray inherited = InheritsFrom.Vector;
1884 if (index < inherited.Count)
1885 return inherited [index];
1894 throw new ArgumentOutOfRangeException ();
1896 // Only copy the vector if we're actually modifying it.
1898 if (this [index] != value) {
1899 initialize_vector ();
1901 vector [index] = value;
1907 // If you explicitly convert the MyBitVector to a BitArray, you will get a deep
1908 // copy of the bit vector.
1910 public static explicit operator BitArray (MyBitVector vector)
1912 vector.initialize_vector ();
1913 return vector.Vector;
1917 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1918 // different size than the current one.
1920 public void Or (MyBitVector new_vector)
1922 // Treat null 'new_vector' as all false, just like the And() below
1923 if (new_vector == null)
1925 BitArray new_array = new_vector.Vector;
1927 initialize_vector ();
1930 if (vector.Count < new_array.Count)
1931 upper = vector.Count;
1933 upper = new_array.Count;
1935 for (int i = 0; i < upper; i++)
1936 vector [i] = vector [i] | new_array [i];
1940 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
1941 // a different size than the current one.
1943 public void And (MyBitVector new_vector)
1947 if (new_vector != null)
1948 new_array = new_vector.Vector;
1950 new_array = new BitArray (Count, false);
1952 initialize_vector ();
1955 if (vector.Count < new_array.Count)
1956 lower = upper = vector.Count;
1958 lower = new_array.Count;
1959 upper = vector.Count;
1962 for (int i = 0; i < lower; i++)
1963 vector [i] = vector [i] & new_array [i];
1965 for (int i = lower; i < upper; i++)
1969 public static void And (ref MyBitVector target, MyBitVector vector)
1972 target.And (vector);
1974 target = vector.Clone ();
1977 public static void Or (ref MyBitVector target, MyBitVector vector)
1982 target = vector.Clone ();
1986 // This does a deep copy of the bit vector.
1988 public MyBitVector Clone ()
1990 MyBitVector retval = new MyBitVector (Count);
1992 retval.Vector = Vector;
2001 else if (!is_dirty && (InheritsFrom != null))
2002 return InheritsFrom.Vector;
2004 initialize_vector ();
2010 initialize_vector ();
2012 for (int i = 0; i < System.Math.Min (vector.Count, value.Count); i++)
2013 vector [i] = value [i];
2017 void initialize_vector ()
2022 vector = new BitArray (Count, false);
2023 if (InheritsFrom != null)
2024 Vector = InheritsFrom.Vector;
2029 public override string ToString ()
2031 StringBuilder sb = new StringBuilder ("{");
2033 BitArray vector = Vector;
2036 for (int i = 0; i < vector.Count; i++) {
2037 sb.Append (vector [i] ? "1" : "0");
2041 return sb.ToString ();