Fix problem in mis-identifying cycles in slices.
[dyninst.git] / dataflowAPI / src / SymEval.C
1 /*
2  * Copyright (c) 1996-2007 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
30  */
31
32 #include <string>
33 #include <iostream>
34
35 #include "../h/SymEval.h"
36 #include "SymEvalPolicy.h"
37
38 #include "AST.h"
39
40 #include "parseAPI/h/CFG.h"
41
42 #include "../rose/x86InstructionSemantics.h"
43 #include "../rose/powerpcInstructionSemantics.h"
44 #include "../rose/SgAsmInstruction.h"
45 #include "../h/stackanalysis.h"
46 #include "SymEvalVisitors.h"
47
48 #include "RoseInsnFactory.h"
49 #include "SymbolicExpansion.h"
50
51 #include "../h/Absloc.h"
52
53 #include "../h/slicing.h" // SliceNode
54
55 #include "debug_dataflow.h"
56
57 using namespace Dyninst;
58 using namespace InstructionAPI;
59 using namespace DataflowAPI;
60
61
62 AST::Ptr SymEval::expand(const Assignment::Ptr &assignment) {
63   // This is a shortcut version for when we only want a
64   // single assignment
65   
66   Result_t res;
67   // Fill it in to mark it as existing
68   res[assignment] = AST::Ptr();
69   expand(res);
70   return res[assignment];
71 }
72
73 void SymEval::expand(Result_t &res, bool applyVisitors) {
74   // Symbolic evaluation works off an Instruction
75   // so we have something to hand to ROSE. 
76   for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
77     if (i->second != AST::Ptr()) {
78       // Must've already filled it in from a previous instruction crack
79       continue;
80     }
81     Assignment::Ptr ptr = i->first;
82     
83     expandInsn(ptr->insn(),
84                ptr->addr(),
85                res);
86   }
87
88   if (applyVisitors) {
89     // Must apply the visitor to each filled in element
90     for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
91       if (!i->second) continue;
92       AST::Ptr tmp = simplifyStack(i->second, i->first->addr(), i->first->func());
93       BooleanVisitor b;
94       AST::Ptr tmp2 = tmp->accept(&b);
95       i->second = tmp2;
96     }
97   }
98 }
99
100 static const int UNLABELED = 0;
101 static const int VISITING = 1;
102 static const int VISITED = 2;
103
104 void dfs(Node::Ptr source,
105          std::map<Node::Ptr, int> &state,
106          std::set<Edge::Ptr> &skipEdges) {
107
108    // DFS from the node given by source
109    // If we meet a node twice without having to backtrack first,
110    // insert that incoming edge into skipEdges.
111    //
112    // Rough idea:
113    // Let preVisit be when a node is first visited
114    // Let postVisit be after all of a node's children were visited
115    // At preVisit set a node to be VISITING
116    // At postVisit set a node to be VISITED
117    // If a node is in VISITING at preVisit we have a cycle
118
119    EdgeIterator b, e;
120    source->outs(b, e);
121    for (; b != e; ++b) {
122       Edge::Ptr edge = *b;
123       Node::Ptr cur = edge->target();
124       
125       if (state[cur] == VISITING) {
126          skipEdges.insert(edge);
127       }
128       else {
129          state[cur] = VISITING;
130          dfs(cur, state, skipEdges);
131          state[cur] = VISITED;
132       }
133    }
134 }
135
136 // Do the previous, but use a Graph as a guide for
137 // performing forward substitution on the AST results
138 void SymEval::expand(Graph::Ptr slice, Result_t &res) {
139     //cout << "Calling expand" << endl;
140     // Other than the substitution this is pretty similar to the first example.
141     NodeIterator gbegin, gend;
142     slice->entryNodes(gbegin, gend);
143
144     std::queue<Node::Ptr> worklist;
145     std::queue<Node::Ptr> dfs_worklist;
146     for (; gbegin != gend; ++gbegin) {
147       expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
148       worklist.push(*gbegin);
149       dfs_worklist.push(*gbegin);
150     }
151
152     /* First, we'll do DFS to check for circularities in the graph;
153      * if so, mark them so we don't do infinite substitution */
154     std::set<Edge::Ptr> skipEdges;
155
156     while (!dfs_worklist.empty()) {
157        Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
158        std::map<Node::Ptr, int> state;
159        state[ptr] = VISITING;
160        dfs(ptr, state, skipEdges);
161     }
162     
163     /* have a list
164      * for each node, process
165      * if processessing succeeded, remove the element
166      * if the size of the list has changed, continue */
167
168     while (!worklist.empty()) {
169       Node::Ptr ptr = worklist.front(); worklist.pop();
170       SliceNode::Ptr aNode = dyn_detail::boost::static_pointer_cast<SliceNode>(ptr);
171       if (!aNode) continue; // They need to be SliceNodes
172       
173       if (!aNode->assign()) continue; // Could be a widen point
174       
175       expand_cerr << "Visiting node " << aNode->assign()->format() << endl;
176
177       AST::Ptr prev = res[aNode->assign()];
178       
179       process(aNode, res, skipEdges); 
180     
181       AST::Ptr post = res[aNode->assign()];
182
183       if (post && !(post->equals(prev))) {
184         // Oy
185         expand_cerr << "Adding successors to list, as new expansion " << endl
186                     << "\t" << post->format() << endl 
187                     << " != " << endl
188                     << "\t" << (prev ? prev->format() : "<NULL>") << endl;
189         NodeIterator oB, oE;
190         aNode->outs(oB, oE);
191         for (; oB != oE; ++oB) {
192           worklist.push(*oB);
193         }
194       }
195     }
196 }
197
198 void SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
199                          const uint64_t addr,
200                          Result_t &res) {
201
202   SymEvalPolicy policy(res, addr, insn->getArch());
203
204   SgAsmInstruction *roseInsn;
205   switch(insn->getArch()) {
206   case Arch_x86:  {
207     RoseInsnX86Factory fac;
208     roseInsn = fac.convert(insn, addr);
209     
210     SymbolicExpansion exp;
211     exp.expandX86(roseInsn, policy);
212     break;
213   }
214   case Arch_ppc32: {
215     RoseInsnPPCFactory fac;
216     roseInsn = fac.convert(insn, addr);
217
218     SymbolicExpansion exp;
219     exp.expandPPC(roseInsn, policy);
220     break;
221   }
222   default:
223     assert(0 && "Unimplemented symbolic expansion architecture");
224     break;
225   }
226   return;
227 }
228
229
230 bool SymEval::process(SliceNode::Ptr ptr,
231                       Result_t &dbase,
232                       std::set<Edge::Ptr> &skipEdges) {
233     bool ret = false;
234     
235     std::map<AbsRegion, Assignment::Ptr> inputMap;
236
237     expand_cerr << "Calling process on " << ptr->format() << endl;
238
239     // Don't try an expansion of a widen node...
240     if (!ptr->assign()) return ret;
241
242     EdgeIterator begin, end;
243     ptr->ins(begin, end);
244
245     for (; begin != end; ++begin) {
246        SliceEdge::Ptr edge = dyn_detail::boost::static_pointer_cast<SliceEdge>(*begin);
247        SliceNode::Ptr source = dyn_detail::boost::static_pointer_cast<SliceNode>(edge->source());
248
249        // Skip this one to break a cycle.
250        if (skipEdges.find(edge) != skipEdges.end()) continue;
251        
252        Assignment::Ptr assign = source->assign();
253        if (!assign) continue; // widen node
254        
255        expand_cerr << "Assigning input " << edge->data().format() 
256                    << " from assignment " << assign->format() << endl;
257        if (inputMap.find(edge->data()) == inputMap.end()) {
258           inputMap[edge->data()] = assign;
259        }
260        else {
261           // Need join operator!
262           expand_cerr << "\t Overlap in inputs, setting to null assignment pointer" << endl;
263           inputMap[edge->data()] = Assignment::Ptr(); // Null equivalent
264        }
265     }
266     
267     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
268     
269     // All of the expanded inputs are in the parameter dbase
270     // If not (like this one), add it
271
272     AST::Ptr ast = SymEval::expand(ptr->assign());
273     //expand_cerr << "\t ... resulting in " << dbase.format() << endl;
274
275     // We have an AST. Now substitute in all of its predecessors.
276     for (std::map<AbsRegion, Assignment::Ptr>::iterator iter = inputMap.begin();
277          iter != inputMap.end(); ++iter) {
278        if (!iter->second) {
279           // Colliding definitions; skip.
280           //cerr << "Skipping subsitution for input " << iter->first << endl;
281           continue;
282        }
283        expand_cerr << "Substituting input " << iter->first << " with assignment " << iter->second->format() << endl;
284        // The region used by the current assignment...
285        const AbsRegion &reg = iter->first;
286        
287        // Create an AST around this one
288        VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
289        
290        // And substitute whatever we have in the database for that AST
291        AST::Ptr definition = dbase[iter->second];
292        
293        if (!definition) {
294           // Can happen if we're expanding out of order, and is generally harmless.
295           continue;
296        }
297        
298        expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
299        
300        if (!ast) {
301           expand_cerr << "Skipping substitution because of null AST" << endl;
302        } else {
303           ast = AST::substitute(ast, use, definition);
304           ret = true;
305        }        
306        //expand_cerr << "\t result is " << res->format() << endl;
307     }
308     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " << (ast ? ast->format() : "<NULL AST>") << endl;
309     
310     // And attempt simplification again
311     ast = simplifyStack(ast, ptr->addr(), ptr->func());
312     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
313                 << (ast ? ast->format() : "<NULL AST>") << endl;
314     
315     dbase[ptr->assign()] = ast;
316     return ret;
317 }
318
319 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func) {
320   if (!ast) return ast;
321   // Let's experiment with simplification
322   StackAnalysis sA(func);
323   StackAnalysis::Height sp = sA.findSP(addr);
324   StackAnalysis::Height fp = sA.findFP(addr);
325   
326   StackVisitor sv(addr, func, sp, fp);
327
328   AST::Ptr simplified = ast->accept(&sv);
329
330   return simplified;
331 }