namespace Mono.CSharp
{
- public enum TriState : byte {
- // Never < Sometimes < Always
- Never,
- Sometimes,
- Always
- }
-
// <summary>
// A new instance of this class is created every time a new block is resolved
// and if there's branching in the block's control flow.
Finally
}
- public sealed class Reachability
- {
- TriState returns, throws, barrier;
-
- public TriState Returns {
- get { return returns; }
- }
- public TriState Throws {
- get { return throws; }
- }
- public TriState Barrier {
- get { return barrier; }
- }
-
- Reachability (TriState returns, TriState throws, TriState barrier)
- {
- this.returns = returns;
- this.throws = throws;
- this.barrier = barrier;
- }
-
- public Reachability Clone ()
- {
- return new Reachability (returns, throws, barrier);
- }
-
- public static TriState TriState_Meet (TriState a, TriState b)
- {
- // (1) if both are Never, return Never
- // (2) if both are Always, return Always
- // (3) otherwise, return Sometimes
- // note that (3) => (3') if both are Sometimes, return Sometimes
- return a == b ? a : TriState.Sometimes;
- }
-
- public static TriState TriState_Max (TriState a, TriState b)
- {
- return ((byte) a > (byte) b) ? a : b;
- }
-
- public void Meet (Reachability b)
- {
- if ((AlwaysReturns && b.AlwaysHasBarrier) || (AlwaysHasBarrier && b.AlwaysReturns))
- returns = TriState.Always;
- else
- returns = TriState_Meet (returns, b.returns);
-
- throws = TriState_Meet (throws, b.throws);
- barrier = TriState_Meet (barrier, b.barrier);
- }
-
- public void Or (Reachability b)
- {
- returns = TriState_Max (returns, b.returns);
- throws = TriState_Max (throws, b.throws);
- barrier = TriState_Max (barrier, b.barrier);
- }
-
- public static Reachability Always ()
- {
- return new Reachability (TriState.Never, TriState.Never, TriState.Never);
- }
-
- TriState Unreachable {
- get { return TriState_Max (returns, TriState_Max (throws, barrier)); }
- }
-
- TriState Reachable {
- get {
- TriState unreachable = Unreachable;
- if (unreachable == TriState.Sometimes)
- return TriState.Sometimes;
- return unreachable == TriState.Always ? TriState.Never : TriState.Always;
- }
- }
-
- public bool AlwaysReturns {
- get { return returns == TriState.Always; }
- }
-
- public bool AlwaysThrows {
- get { return throws == TriState.Always; }
- }
-
- public bool AlwaysHasBarrier {
- get { return barrier == TriState.Always; }
- }
-
- public bool IsUnreachable {
- get { return Unreachable == TriState.Always; }
- }
-
- public void SetReturns ()
- {
- returns = TriState.Always;
- }
-
- public void SetThrows ()
- {
- throws = TriState.Always;
- }
-
- public void SetBarrier ()
- {
- barrier = TriState.Always;
- }
-
- static string ShortName (TriState returns)
- {
- switch (returns) {
- case TriState.Never:
- return "N";
- case TriState.Sometimes:
- return "S";
- default:
- return "A";
- }
- }
-
- public override string ToString ()
- {
- return String.Format ("[{0}:{1}:{2}:{3}]",
- ShortName (returns), ShortName (throws), ShortName (barrier),
- ShortName (Reachable));
- }
- }
-
public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
{
switch (type) {
// Private.
//
MyBitVector locals, parameters;
- Reachability reachability;
+ bool is_unreachable;
static int next_id = 0;
int id;
? MyBitVector.Empty
: new MyBitVector (parent == null ? MyBitVector.Empty : parent.parameters, num_params);
- reachability = parent == null ? Reachability.Always () : parent.Reachability.Clone ();
+ if (parent != null)
+ is_unreachable = parent.is_unreachable;
id = ++next_id;
+
}
public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
: this (type, parent, block, loc, parent.CountParameters, parent.CountLocals)
{ }
- public UsageVector (MyBitVector parameters, MyBitVector locals, Reachability reachability, Block block, Location loc)
+ private UsageVector (MyBitVector parameters, MyBitVector locals, bool is_unreachable, Block block, Location loc)
{
this.Type = SiblingType.Block;
this.Location = loc;
this.Block = block;
- this.reachability = reachability;
+ this.is_unreachable = is_unreachable;
+
this.parameters = parameters;
this.locals = locals;
id = ++next_id;
+
}
// <summary>
retval.locals = locals.Clone ();
retval.parameters = parameters.Clone ();
- retval.reachability = reachability.Clone ();
+ retval.is_unreachable = is_unreachable;
return retval;
}
public bool IsAssigned (VariableInfo var, bool ignoreReachability)
{
- if (!ignoreReachability && !var.IsParameter && Reachability.IsUnreachable)
+ if (!ignoreReachability && !var.IsParameter && IsUnreachable)
return true;
return var.IsAssigned (var.IsParameter ? parameters : locals);
public void SetAssigned (VariableInfo var)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!var.IsParameter && IsUnreachable)
return;
var.SetAssigned (var.IsParameter ? parameters : locals);
public bool IsFieldAssigned (VariableInfo var, string name)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!var.IsParameter && IsUnreachable)
return true;
return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
public void SetFieldAssigned (VariableInfo var, string name)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!var.IsParameter && IsUnreachable)
return;
var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
}
- public Reachability Reachability {
- get { return reachability; }
- }
-
- public void Return ()
- {
- if (!reachability.IsUnreachable)
- reachability.SetReturns ();
+ public bool IsUnreachable {
+ get { return is_unreachable; }
}
- public void Throw ()
+ public void ResetBarrier ()
{
- if (!reachability.IsUnreachable) {
- reachability.SetThrows ();
- reachability.SetBarrier ();
- }
+ is_unreachable = false;
}
public void Goto ()
{
- if (!reachability.IsUnreachable)
- reachability.SetBarrier ();
+ is_unreachable = true;
}
public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
MyBitVector locals = null;
MyBitVector parameters = null;
- Reachability reachability = null;
+ bool is_unreachable = sibling_list.is_unreachable;
- for (UsageVector child = sibling_list; child != null; child = child.Next) {
- Report.Debug (2, " MERGING SIBLING ", reachability, child);
+ if (!sibling_list.IsUnreachable) {
+ locals &= sibling_list.locals;
+ parameters &= sibling_list.parameters;
+ }
- if (reachability == null)
- reachability = child.Reachability.Clone ();
- else
- reachability.Meet (child.Reachability);
-
- // A local variable is initialized after a flow branching if it
- // has been initialized in all its branches which do neither
- // always return or always throw an exception.
- //
- // If a branch may return, but does not always return, then we
- // can treat it like a never-returning branch here: control will
- // only reach the code position after the branching if we did not
- // return here.
- //
- // It's important to distinguish between always and sometimes
- // returning branches here:
- //
- // 1 int a;
- // 2 if (something) {
- // 3 return;
- // 4 a = 5;
- // 5 }
- // 6 Console.WriteLine (a);
- //
- // The if block in lines 3-4 always returns, so we must not look
- // at the initialization of `a' in line 4 - thus it'll still be
- // uninitialized in line 6.
- //
- // On the other hand, the following is allowed:
- //
- // 1 int a;
- // 2 if (something)
- // 3 a = 5;
- // 4 else
- // 5 return;
- // 6 Console.WriteLine (a);
- //
- // Here, `a' is initialized in line 3 and we must not look at
- // line 5 since it always returns.
- //
- bool unreachable = child.Reachability.IsUnreachable;
-
- Report.Debug (2, " MERGING SIBLING #1", reachability,
- child.Type, child.Reachability.IsUnreachable, unreachable);
-
- if (!unreachable)
- locals &= child.locals;
+ for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
+ is_unreachable &= child.is_unreachable;
- // An `out' parameter must be assigned in all branches which do
- // not always throw an exception.
- if (!child.Reachability.AlwaysThrows)
+ if (!child.IsUnreachable) {
+ locals &= child.locals;
parameters &= child.parameters;
-
- Report.Debug (2, " MERGING SIBLING #2", parameters, locals);
+ }
}
-
- if (reachability == null)
- throw new InternalErrorException ("Cannot happen: the loop above runs at least twice");
- return new UsageVector (parameters, locals, reachability, null, loc);
+ return new UsageVector (parameters, locals, is_unreachable, null, loc);
}
// <summary>
// </summary>
public UsageVector MergeChild (UsageVector child, bool overwrite)
{
- Report.Debug (2, " MERGING CHILD EFFECTS", this, child, reachability, Type);
+ Report.Debug (2, " MERGING CHILD EFFECTS", this, child, Type);
- Reachability new_r = child.Reachability;
+ bool new_isunr = child.is_unreachable;
//
// We've now either reached the point after the branching or we will
// we need to look at (see above).
//
- if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
+ if ((Type == SiblingType.SwitchSection) && !new_isunr) {
Report.Error (163, Location,
"Control cannot fall through from one " +
"case label to another");
parameters |= child.parameters;
if (overwrite)
- reachability = new_r.Clone ();
+ is_unreachable = new_isunr;
else
- reachability.Or (new_r);
+ is_unreachable |= new_isunr;
return child;
}
if (o_vectors == null)
return;
- if (reachability.IsUnreachable) {
+ if (IsUnreachable) {
if (locals != null)
locals.SetAll (true);
if (parameters != null)
for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
Report.Debug (1, " MERGING BREAK ORIGIN", vector);
- if (vector.Reachability.IsUnreachable)
+ if (vector.IsUnreachable)
continue;
locals &= vector.locals;
parameters &= vector.parameters;
- reachability.Meet (vector.Reachability);
+ is_unreachable &= vector.is_unreachable;
}
Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
public override string ToString ()
{
- return String.Format ("Vector ({0},{1},{2}-{3}-{4})", Type, id, reachability, parameters, locals);
+ return String.Format ("Vector ({0},{1},{2}-{3}-{4})", Type, id, is_unreachable, parameters, locals);
}
}
actual = CurrentUsageVector.Clone ();
// stand-in for backward jumps
- CurrentUsageVector.Reachability.Meet (Reachability.Always ());
+ CurrentUsageVector.ResetBarrier ();
}
public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
{
UsageVector vector = base.Merge ();
- if (actual.Reachability.IsUnreachable)
+ if (actual.IsUnreachable)
Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
actual.MergeChild (vector, false);
// </summary>
void CheckOutParameters (UsageVector vector, Location loc)
{
- if (vector.Reachability.IsUnreachable)
+ if (vector.IsUnreachable)
return;
for (int i = 0; i < param_map.Count; i++) {
VariableInfo var = param_map [i];
return vector;
}
- public Reachability End ()
+ public bool End ()
{
- return Merge ().Reachability;
+ return Merge ().IsUnreachable;
}
}
ArrayList non_public_fields = new ArrayList ();
if (fields != null) {
- foreach (FieldMember field in fields) {
+ foreach (FieldBase field in fields) {
if ((field.ModFlags & Modifiers.STATIC) != 0)
continue;
if ((field.ModFlags & Modifiers.PUBLIC) != 0)
public readonly int Count;
public static readonly MyBitVector Empty = new MyBitVector ();
+ // Invariant: vector != null => vector.Count == Count
+ // Invariant: vector == null || shared == null
+ // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
+ // The object in 'shared' cannot be modified, while 'vector' can be freely modified
BitArray vector, shared;
MyBitVector ()
{
- vector = null;
shared = new BitArray (0, false);
- Count = 0;
}
public MyBitVector (MyBitVector InheritsFrom, int Count)
{
- vector = null;
- shared = InheritsFrom == null ? null : InheritsFrom.Shared;
+ if (InheritsFrom != null)
+ shared = InheritsFrom.Shared;
+
this.Count = Count;
}
+ // Use this accessor to get a shareable copy of the underlying BitArray representation
BitArray Shared {
get {
+ // Post-condition: vector == null
if (shared == null) {
shared = vector;
vector = null;
// </summary>
private MyBitVector Or (MyBitVector new_vector)
{
- int min = new_vector.Count;
+ if (Count == 0 || new_vector.Count == 0)
+ return this;
+
+ BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
+
+ if (o == null) {
+ int n = new_vector.Count;
+ if (n < Count) {
+ for (int i = 0; i < n; ++i)
+ this [i] = true;
+ } else {
+ SetAll (true);
+ }
+ return this;
+ }
+
+ if (Count == o.Count) {
+ if (vector == null) {
+ if (shared == null)
+ return this;
+ initialize_vector ();
+ }
+ vector.Or (o);
+ return this;
+ }
+
+ int min = o.Count;
if (Count < min)
min = Count;
- for (int i = 0; i < min; i++)
- this [i] |= new_vector [i];
+ for (int i = 0; i < min; i++) {
+ if (o [i])
+ this [i] = true;
+ }
return this;
}
// <summary>
- // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
+ // Performs an `and' operation on the bit vector. The `new_vector' may have
// a different size than the current one.
// </summary>
private MyBitVector And (MyBitVector new_vector)
{
- int min = new_vector.Count;
+ if (Count == 0)
+ return this;
+
+ BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
+
+ if (o == null) {
+ for (int i = new_vector.Count; i < Count; ++i)
+ this [i] = false;
+ return this;
+ }
+
+ if (o.Count == 0) {
+ SetAll (false);
+ return this;
+ }
+
+ if (Count == o.Count) {
+ if (vector == null) {
+ if (shared == null) {
+ shared = new_vector.Shared;
+ return this;
+ }
+ initialize_vector ();
+ }
+ vector.And (o);
+ return this;
+ }
+
+ int min = o.Count;
if (Count < min)
min = Count;
- for (int i = 0; i < min; i++)
- this [i] &= new_vector [i];
+ for (int i = 0; i < min; i++) {
+ if (! o [i])
+ this [i] = false;
+ }
for (int i = min; i < Count; i++)
this [i] = false;
public static MyBitVector operator & (MyBitVector a, MyBitVector b)
{
- if (a == null && b == null)
- return null;
+ if (a == b)
+ return a;
if (a == null)
return b.Clone ();
if (b == null)
public static MyBitVector operator | (MyBitVector a, MyBitVector b)
{
- if (a == null && b == null)
- return null;
+ if (a == b)
+ return a;
if (a == null)
return new MyBitVector (null, b.Count);
if (b == null)
void initialize_vector ()
{
+ // Post-condition: vector != null
if (shared == null) {
vector = new BitArray (Count, true);
return;
}
- vector = new BitArray (Count, false);
-
- int min = shared.Count;
- if (min > Count)
- min = Count;
-
- for (int i = 0; i < min; i++)
- vector [i] = shared [i];
-
+ vector = new BitArray (shared);
+ if (Count != vector.Count)
+ vector.Length = Count;
shared = null;
}