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;
31 using Mono.CodeContracts.Static.AST;
32 using Mono.CodeContracts.Static.AST.Visitors;
33 using Mono.CodeContracts.Static.Analysis.HeapAnalysis.SymbolicGraph;
34 using Mono.CodeContracts.Static.ControlFlow;
35 using Mono.CodeContracts.Static.DataFlowAnalysis;
36 using Mono.CodeContracts.Static.DataStructures;
37 using Mono.CodeContracts.Static.Providers;
39 namespace Mono.CodeContracts.Static.Analysis.HeapAnalysis {
40 class HeapAnalysis : IAnalysis<APC, Domain, IILVisitor<APC, int, int, Domain, Domain>, Dummy> {
41 private readonly Dictionary<Pair<APC, APC>, IImmutableMap<SymbolicValue, LispList<SymbolicValue>>> forwardRenamings =
42 new Dictionary<Pair<APC, APC>, IImmutableMap<SymbolicValue, LispList<SymbolicValue>>> ();
44 public readonly Dictionary<APC, IMergeInfo> MergeInfoCache = new Dictionary<APC, IMergeInfo> ();
45 public readonly DoubleDictionary<APC, APC, Dummy> RenamePoints = new DoubleDictionary<APC, APC, Dummy> ();
46 private readonly ICodeLayer<int, int, IStackContextProvider, Dummy> stackLayer;
47 private IFixPointInfo<APC, Domain> fixPointInfo;
49 public HeapAnalysis (ICodeLayer<int, int, IStackContextProvider, Dummy> stackLayer)
51 this.stackLayer = stackLayer;
54 public IStackContextProvider StackContextProvider
56 get { return this.stackLayer.ILDecoder.ContextProvider; }
59 public IMetaDataProvider MetaDataProvider
61 get { return this.stackLayer.MetaDataProvider; }
64 public IContractProvider ContractProvider
66 get { return this.stackLayer.ContractProvider; }
69 public Method CurrentMethod
71 get { return this.StackContextProvider.MethodContext.CurrentMethod; }
74 IILVisitor<APC, int, int, Domain, Domain> IAnalysis<APC, Domain, IILVisitor<APC, int, int, Domain, Domain>, Dummy>.
80 public Domain Join (Pair<APC, APC> edge, Domain newstate, Domain prevstate, out bool weaker, bool widen)
82 if (DebugOptions.Debug)
84 Console.WriteLine ("-----OPT Join at {0}", edge);
85 Console.WriteLine ("-----Existing state:");
86 prevstate.Dump (Console.Out);
87 Console.WriteLine ("-----New state:");
88 newstate.Dump (Console.Out);
92 Domain domain = prevstate.Join (newstate, widen, out weaker, out mi);
95 if (this.MergeInfoCache.TryGetValue (edge.Value, out mi2) && mi2 == null)
96 this.MergeInfoCache [edge.Value] = mi;
98 this.MergeInfoCache [edge.Value] = mi;
100 if (DebugOptions.Debug)
102 Console.WriteLine ("-----Result state: changed = {0} (widen = {1})", weaker ? 1 : 0, widen ? 1 : 0);
103 domain.Dump (Console.Out);
104 Console.WriteLine ("----------------------------------------------");
110 public Domain ImmutableVersion (Domain arg)
112 return arg.ImmutableVersion ();
115 public Domain MutableVersion (Domain arg)
122 public Domain EdgeConversion (APC @from, APC to, bool isJoinPoint, Dummy data, Domain state)
125 this.RenamePoints [from, to] = Dummy.Value;
126 if (!this.MergeInfoCache.ContainsKey (to))
127 this.MergeInfoCache.Add (to, null);
130 if (DebugOptions.Debug)
132 Console.WriteLine ("----Edge conversion on {0}->{1}------", from, to);
133 state.Dump (Console.Out);
134 Console.WriteLine ("-------------------------------------");
140 public bool IsBottom (APC pc, Domain state)
142 return state.IsBottom;
145 public Predicate<APC> SaveFixPointInfo (IFixPointInfo<APC, Domain> fixPointInfo)
147 this.fixPointInfo = fixPointInfo;
151 public void Dump (Pair<Domain, TextWriter> pair)
153 pair.Key.Dump (pair.Value);
156 private IILVisitor<APC, int, int, Domain, Domain> GetVisitor ()
158 return new AnalysisDecoder (this);
161 public Domain InitialValue ()
163 return new Domain (this);
166 public IILDecoder<APC, SymbolicValue, SymbolicValue, IValueContextProvider<SymbolicValue>, IImmutableMap<SymbolicValue, LispList<SymbolicValue>>>
167 GetDecoder<Context>(IILDecoder<APC, int, int, Context, Dummy> underlying)
168 where Context : IStackContextProvider
170 return new ValueDecoder<Context> (this, underlying);
173 public bool IsUnreachable (APC pc)
176 if (!this.fixPointInfo.PreStateLookup (pc, out domain) || domain.IsBottom)
182 public IImmutableMap<SymbolicValue, LispList<SymbolicValue>> EdgeRenaming (Pair<APC, APC> edge, bool isJoinPoint)
184 IImmutableMap<SymbolicValue, LispList<SymbolicValue>> forwardRenaming;
186 if (this.forwardRenamings.TryGetValue (edge, out forwardRenaming))
187 return forwardRenaming;
189 IImmutableMap<SymbolicValue, LispList<SymbolicValue>> renaming = null;
191 PostStateLookup (edge.Key, out afterBegin);
192 if (afterBegin == null || afterBegin.IsBottom)
195 PreStateLookup (edge.Value, out beforeEnd);
196 if (beforeEnd != null) {
197 IImmutableMap<SymValue, LispList<SymValue>> forward;
198 if (!TryComputeFromJoinCache (afterBegin, beforeEnd, edge.Value, out forward)) {
199 IImmutableMap<SymValue, SymValue> backward;
200 if (!afterBegin.LessEqual (beforeEnd, out forward, out backward))
201 throw new InvalidOperationException ("Should never happen");
202 if (isJoinPoint && forward == null)
203 forward = afterBegin.GetForwardIdentityMap ();
205 if (forward != null) {
206 renaming = ImmutableIntKeyMap<SymbolicValue, LispList<SymbolicValue>>.Empty (SymbolicValue.GetUniqueKey);
207 foreach (SymValue sv in forward.Keys) {
208 LispList<SymbolicValue> targets = null;
209 foreach (SymValue target in forward [sv].AsEnumerable ())
210 targets = targets.Cons (new SymbolicValue (target));
212 renaming = renaming.Add (new SymbolicValue (sv), targets);
216 this.forwardRenamings.Add (edge, renaming);
220 private bool TryComputeFromJoinCache (Domain inDomain, Domain outDomain, APC joinPoint, out IImmutableMap<SymValue, LispList<SymValue>> forward)
224 if (this.MergeInfoCache.TryGetValue (joinPoint, out mi) && mi != null && outDomain.IsResultEGraph (mi)) {
225 if (inDomain.IsGraph1 (mi)) {
226 forward = mi.ForwardG1Map;
229 if (inDomain.IsGraph2 (mi)) {
230 forward = mi.ForwardG2Map;
237 public Domain GetPreState (APC pc)
240 PreStateLookup (pc, out domain);
244 public bool PreStateLookup (APC pc, out Domain ifFound)
246 return this.fixPointInfo.PreStateLookup (pc, out ifFound);
249 public bool PostStateLookup (APC pc, out Domain ifFound)
251 return this.fixPointInfo.PostStateLookup (pc, out ifFound);