2 // ForwardDataFlowAnalysisBase.cs
5 // Alexander Chebaturkin (chebaturkin@gmail.com)
7 // Copyright (C) 2011 Alexander Chebaturkin
9 // Permission is hereby granted, free of charge, to any person obtaining
10 // a copy of this software and associated documentation files (the
11 // "Software"), to deal in the Software without restriction, including
12 // without limitation the rights to use, copy, modify, merge, publish,
13 // distribute, sublicense, and/or sell copies of the Software, and to
14 // permit persons to whom the Software is furnished to do so, subject to
15 // the following conditions:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 using System.Collections.Generic;
30 using Mono.CodeContracts.Static.ControlFlow;
31 using Mono.CodeContracts.Static.DataStructures;
33 namespace Mono.CodeContracts.Static.DataFlowAnalysis {
34 abstract class ForwardDataFlowAnalysisBase<AState> : DataFlowAnalysisBase<AState> {
35 private readonly Dictionary<APC, AState> post_state = new Dictionary<APC, AState> ();
37 protected ForwardDataFlowAnalysisBase (ICFG cfg) : base (cfg)
41 public bool GetPreState (APC pc, out AState state)
44 state = GetPreState (pc, default(AState), out noInfo);
48 public AState GetPreStateWithDefault (APC apc, AState ifMissing)
51 AState preState = GetPreState (apc, default(AState), out noInfo);
52 return noInfo ? ifMissing : preState;
55 private AState GetPreState (APC apc, AState ifMissing, out bool noInfo)
57 LispList<APC> rest = null;
59 APC singlePredecessor;
62 while (!(weHaveState = this.JoinState.TryGetValue (tmp, out state)) &&
63 !RequiresJoining (tmp) && this.CFG.HasSinglePredecessor (tmp, out singlePredecessor)) {
64 tmp = singlePredecessor;
66 rest = rest.Cons (tmp);
74 bool listWasNotEmpty = rest != null;
75 while (rest != null) {
76 if (IsBottom (rest.Head, state)) {
80 state = MutableVersion (state, rest.Head);
81 state = Transfer (rest.Head, state);
82 if (IsBottom (rest.Head, state)) {
89 this.JoinState.Add (rest.Head, ImmutableVersion (state, rest.Head));
93 this.JoinState.Add (apc, ImmutableVersion (state, apc));
99 public bool GetPostState (APC apc, out AState result)
101 if (this.post_state.TryGetValue (apc, out result))
105 if (apc.Block.Count <= apc.Index)
106 return GetPreState (apc, out result);
108 if (this.CFG.HasSingleSuccessor (apc, out singleSuccessor) && !RequiresJoining (singleSuccessor))
109 return GetPreState (singleSuccessor, out result);
112 if (!GetPreState (apc, out ifFound))
115 result = MutableVersion (ifFound, apc);
116 result = Transfer (apc, result);
118 this.post_state.Add (apc, result);
122 public void Run (AState startState)
124 Initialize (this.CFG.Entry, startState);
128 protected override int WorkingListComparer (APC a, APC b)
130 return b.Block.ReversePostOrderIndex - a.Block.ReversePostOrderIndex;
133 protected override bool RequiresJoining (APC pc)
135 return this.CFG.IsJoinPoint (pc);
138 protected override bool HasSingleSuccessor (APC pc, out APC next)
140 return this.CFG.HasSingleSuccessor (pc, out next);
143 protected override IEnumerable<APC> Successors (APC pc)
145 return this.CFG.Successors (pc);
148 protected override bool IsBackEdge (APC from, APC to)
150 //todo: implement this
151 //can't be false, because back edges means having cycles, so we definitely have to widen