Change slice interface to allow choose whether control flow dependenc or stack analys...
[dyninst.git] / dataflowAPI / src / slicing.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30 #include <set>
31 #include <vector>
32 #include <map>
33 #include <utility>
34 #include "dataflowAPI/h/Absloc.h"
35 #include "dataflowAPI/h/AbslocInterface.h"
36 #include "Instruction.h"
37
38 #include "dataflowAPI/h/stackanalysis.h"
39 #include "dataflowAPI/h/slicing.h"
40 #include "ABI.h"
41 #include "bitArray.h"
42
43
44 #include "common/h/Graph.h"
45 #include "instructionAPI/h/Instruction.h"
46 #include "instructionAPI/h/InstructionDecoder.h"
47
48 #include "debug_dataflow.h"
49
50 #include "parseAPI/h/CFG.h"
51 #include "parseAPI/h/CodeSource.h"
52 #include "parseAPI/h/CodeObject.h"
53
54 #include <boost/bind.hpp>
55
56 #include <ctime>
57
58 using namespace Dyninst;
59 using namespace InstructionAPI;
60 using namespace std;
61 using namespace ParseAPI;
62
63 bool containsCall(ParseAPI::Block *);
64 bool containsRet(ParseAPI::Block *);
65 ParseAPI::Function *getEntryFunc(ParseAPI::Block *);
66
67 /* An algorithm to generate a slice graph.
68  
69 The slice graph is a directed graph that consists of nodes
70 corresponding to assignments from a set of inputs to an
71 output, where each input or output is an `abstract region'
72 (AbsRegion class) describing a register or a stack or heap
73 location. Edges in the slice graph indicate flow from the
74 output AbsRegion of the source node to an input AbsRegion of
75 the target node. Edges are typed with an AbsRegion
76 corresponding to the input region the flow describes; this
77 edge typing is necessary because two AbsRegions in different
78 assignments may be refer to equivalent locations without
79 being identical---consider, for example, the transformation
80 of stack locations across function calls in interprocedural
81 slices.
82
83 Implementation details:
84
85 The slicing algorithm searches either forward or backward
86 from an initial assignment in the CFG, with the search
87 termination controlled in part by a set of user-provided
88 predicates (indicating, e.g., whether to follow call edges).
89 At each step, the slicer maintains an `active' set of
90 AbsRegions for which we are searching for related
91 assignments (uses, in the forward case; definitions, in the
92 backward case); this set is updated as the search
93 progresses. The graph is linked up on the way "down" the
94 slice recursion.
95
96 To avoid redundantly revisiting "down-slice" instructions
97 due to forks in the CFG, AbsRegion assignments are cached as
98 the search completes recursion down a particular branch.
99 Because CFGs are loopy directeg graphs, however, this does
100 not lead to an optimimal search ordering; it is possible to
101 construct pathological cases in which down-slice edges are
102 visited multiple times due to novel AbsRegions arising on
103 different paths. The caching of down-slice AbsRegions only 
104 guarantees that a particular AbsRegion is only searched for
105 once along a given path---the loopy nature of the graph
106 prevents optimal search stragegies such as a topologically
107 sorted ordering that would be possible in a DAG. 
108
109 The algorithm goes more or less like this:
110
111    A_0 <- initial assignment 
112    F <- initialize frame from active AbsRegions in A_0
113    // F contains `active' set of AbsRegions
114    
115    sliceInternalAux( F ) :
116      
117       // find assignments in the current instruction,
118       // add them to the graph if appropriate, update
119       // the active set:
120       // active <- active \ killed U matches
121       updateAndLink(F)
122   
123       // `successor' is direction-appropriate 
124       foreach successor NF of F
125          if visited(F->NF) // edge visited    
126             
127             // try to add assignments cached from down-slice
128             updateAndLinkFromCache(NF)
129             
130             // remove AbsRegions that have been visited
131             // along this edge from the active set
132             removeBlocked(NF) 
133
134             // active is empty unless this instruction
135             // introduced new active regions (in
136             // updateAndLinkFromCache)
137
138          visited(F->NF) <- true
139          // recurse
140          sliceInternalAux( NF )
141          // merge cached definitions, except those generated
142          // in F
143          cache[F] <- cache[F] U (cache[NF] \ defs[F]
144
145    Clearly the `find successors' bit is quite complicated
146    and involves user-defined predicates and various CFG
147    traversal rules, updating of AbsRegions, etc. Refer to
148    comments in the code for more details.
149 */
150 Graph::Ptr
151 Slicer::sliceInternal(
152     Direction dir,
153     Predicates &p)
154 {
155     static clock_t sliceInternalTime = 0, 
156                    recursiveSliceTime = 0,
157                    t, t0;
158 //    t = clock();
159     Graph::Ptr ret;
160     SliceNode::Ptr aP;
161     SliceFrame initFrame;
162     map<CacheEdge, set<AbsRegion> > visited;
163
164     // this is the unified cache aka the cache that will hold 
165     // the merged set of 'defs'.
166     map<Address,DefCache> cache;
167
168     // this is the single cache aka the cache that holds
169     // only the 'defs' from a single instruction. 
170     map<Address, DefCache> singleCache; 
171     
172     ret = Graph::createGraph();
173
174     // set up a slicing frame describing with the
175     // relevant context
176     constructInitialFrame(dir,initFrame);
177
178     // note that the AbsRegion in this Element *does not matter*;
179     // we just need the block, function and assignment
180     aP = createNode(Element(b_,f_,a_->out(),a_));
181
182     if(dir == forward) {
183         slicing_printf("Inserting entry node %p/%s\n",
184             aP.get(),aP->format().c_str());
185     } else {
186         slicing_printf("Inserting exit node %p/%s\n",
187             aP.get(),aP->format().c_str());
188     }
189
190     // add to graph
191     insertInitialNode(ret, dir, aP);
192     if (p.addNodeCallback(a_,visitedEdges)) {
193         // initialize slice stack and set for loop detection.
194         // the set may be redundant, but speeds up the loopless case.
195         addrStack.push_back(initFrame.addr());
196         addrSet.insert(initFrame.addr());
197         
198         slicing_printf("Starting recursive slicing\n");
199         sliceInternalAux(ret,dir,p,initFrame,true,visited, singleCache, cache);
200         slicing_printf("Finished recursive slicing\n");
201     }
202
203
204     // promote any remaining plausible nodes.
205     promotePlausibleNodes(ret, dir); 
206
207     cleanGraph(ret);
208 //    sliceInternalTime += clock() - t;
209    
210 //    fprintf(stderr, "sliceInternal: %.3lf\n", (float)sliceInternalTime / CLOCKS_PER_SEC);
211 //    fprintf(stderr, "recursiveSlice: %.3lf\n", (float)recursiveSliceTime / CLOCKS_PER_SEC);
212
213 //    fprintf(stderr, "visited: %d, in slice %d, entry visited %d %d\n", cache.size(), ret->size(), cache.find(f_->addr()) != cache.end() , cache.find(f_->entry()->last()) != cache.end());
214     return ret;
215 }
216
217 // main slicing routine. creates any new edges if they are part of the 
218 // slice, and recursively slices on the next isntruction(s).
219 void Slicer::sliceInternalAux(
220     Graph::Ptr g,
221     Direction dir,
222     Predicates &p,
223     SliceFrame &cand,
224     bool skip,              // skip linking this frame; for bootstrapping
225     map<CacheEdge,set<AbsRegion> > & visited,
226     map<Address, DefCache>& singleCache, 
227     map<Address,DefCache> & cache)
228 {
229     vector<SliceFrame> nextCands;
230     DefCache& mydefs = singleCache[cand.addr()];
231
232     slicing_printf("\tslicing from %lx, currently watching %ld regions\n",
233         cand.addr(),cand.active.size());
234
235     // Find assignments at this point that affect the active
236     // region set (if any) and link them into the graph; update
237     // the active set. Returns `true' if any changes are made,
238     // `false' otherwise.
239
240     if (!skip) {
241         if (!updateAndLink(g,dir,cand, mydefs, p)) return;
242             slicing_printf("\t\tfinished udpateAndLink, active.size: %ld\n",
243                        cand.active.size());
244     }
245
246     if (cand.active.empty()) {
247         promotePlausibleNodes(g, dir);
248         return;
249     }
250
251     // Find the next search candidates along the control
252     // flow (for appropriate direction)
253     bool success = getNextCandidates(dir,p,cand,nextCands);
254     if (!success) {
255         widenAll(g,dir,cand);
256     }
257
258     slicing_printf("\t\tgetNextCandidates returned %ld, success: %d\n",
259                    nextCands.size(),success);
260
261     for (unsigned i=0; i < nextCands.size(); ++i) {
262         SliceFrame & f = nextCands[i];
263         if (!f.valid) {
264             widenAll(g,dir,cand);
265             continue;
266         }
267
268         CacheEdge e(cand.addr(),f.addr());
269
270         slicing_printf("\t\t candidate %d is at %lx, %ld active\n",
271                        i,f.addr(),f.active.size());
272
273         if (p.useCache() && visited.find(e) != visited.end()) {
274             // attempt to resolve the current active set
275             // via cached values from down-slice, eliminating
276             // those elements of the active set that can be
277             // so resolved
278
279             // check if in loop, if so, merge single caches into unified.
280             if (addrSet.find(f.addr()) != addrSet.end()) {
281                 mergeRecursiveCaches(singleCache, cache, f.addr());
282             }
283
284             updateAndLinkFromCache(g,dir,f,cache[f.addr()]);
285             removeBlocked(f,visited[e]);
286
287             // the only way this is not true is if the current
288             // search path has introduced new AbsRegions of interest
289             if (f.active.empty()) {
290                 continue;
291             }
292         }
293
294         markVisited(visited,e,f.active);
295
296         // If the control flow search has run
297         // off the rails somehow, widen;
298         // otherwise search down this new path
299         // Xiaozhu: change from 50 to 100 changes my problem,
300         // but it is still adhoc.
301         if(!f.valid || visited.size() > 100*g->size()) {
302             widenAll(g,dir,cand);
303             }
304         else {
305
306             // update stacks
307             addrStack.push_back(f.addr());
308             addrSet.insert(f.addr());
309
310             sliceInternalAux(g,dir,p,f,false,visited, singleCache, cache);
311
312             // clean up stacks
313             addrStack.pop_back();
314             addrSet.erase(f.addr());
315
316             // absorb the down-slice cache into this node's cache
317                 cache[cand.addr()].merge(cache[f.addr()]);
318         }
319     }
320     
321     // promote plausible entry/exit nodes if this is end of recursion.
322     if (nextCands.size() == 0) {
323         promotePlausibleNodes(g, dir);
324     }
325
326     // Replace any definitions from down-slice with
327     // those created by this instruction
328     //
329     // XXX if this instruction has definitions that
330     //     were not of interest when it was visited
331     //     (empty mydefs for that absregion), then
332     //     do not cache down-slice information; if
333     //     a different path leads back to this node,
334     //     we need to create the real definitions
335     cache[cand.addr()].replace(mydefs);
336 }
337
338 void
339 Slicer::removeBlocked(
340     SliceFrame & f,
341     set<AbsRegion> const& block)
342 {
343     SliceFrame::ActiveMap::iterator ait = f.active.begin();
344     for( ; ait != f.active.end(); ) {
345         if(block.find((*ait).first) != block.end()) {
346             SliceFrame::ActiveMap::iterator del = ait;
347             ++ait;
348             f.active.erase(del);
349         } else {
350             ++ait;
351         }
352     }
353 }
354
355 void
356 Slicer::markVisited(
357     map<CacheEdge, set<AbsRegion> > & visited,
358     CacheEdge const& e,
359     SliceFrame::ActiveMap const& active)
360 {
361     set<AbsRegion> & v = visited[e];
362     SliceFrame::ActiveMap::const_iterator ait = active.begin();
363     for( ; ait != active.end(); ++ait) {
364         v.insert((*ait).first);
365     }
366 }
367
368 // converts the current instruction into assignments and looks for matching 
369 // elements in the active map. if any are found, graph nodes and edges are
370 // created. this function also updates the active map to be contain only the
371 // elements that are valid after the above linking (killed defs are removed).
372 bool Slicer::updateAndLink(
373     Graph::Ptr g,
374     Direction dir,
375     SliceFrame & cand,
376     DefCache& cache,
377     Predicates &p)
378 {
379     static clock_t updateAndLinkTime = 0, 
380                    convertInsnTime = 0,
381                    t,tc;
382 //    t = clock();
383
384     vector<Assignment::Ptr> assns;
385     vector<bool> killed;
386     vector<Element> matches;
387     vector<Element> newactive;
388     Instruction::Ptr insn;
389     bool change = false;
390
391     killed.resize(cand.active.size(),false);
392
393     if(dir == forward)
394         insn = cand.loc.current->first;
395     else
396         insn = cand.loc.rcurrent->first;
397
398 //    tc = clock();
399     convertInstruction(insn,cand.addr(),cand.loc.func, cand.loc.block, assns);
400     // iterate over assignments and link matching elements.
401     for(unsigned i=0; i<assns.size(); ++i) {
402         SliceFrame::ActiveMap::iterator ait = cand.active.begin();
403         unsigned j=0;
404         for( ; ait != cand.active.end(); ++ait,++j) {
405             if (findMatch(g,dir,cand,(*ait).first,assns[i],matches, cache)) { // links    
406                 if (!p.addNodeCallback(assns[i], visitedEdges)) return false;
407             }
408             killed[j] = killed[j] || kills((*ait).first,assns[i]);
409             change = change || killed[j];
410         }
411         // Record the *potential* of this instruction to interact
412         // with all possible abstract regions
413         cachePotential(dir,assns[i],cache);
414     }
415
416     if(!change && matches.empty()) {// no change -- nothing killed, nothing added
417 //        updateAndLinkTime += clock() - t;
418 //      fprintf(stderr, "updateAndLink: %.3lf\n", (float)updateAndLinkTime / CLOCKS_PER_SEC);
419         return true;
420     }
421
422     // update of active set -- matches + anything not killed
423     SliceFrame::ActiveMap::iterator ait = cand.active.begin();
424     unsigned j=0;
425     for( ; ait != cand.active.end(); ) {
426         if(killed[j]) {
427             // remove killed nodes from plausible exit set.
428             // this need only be done in the forward case,
429             // because backward slice semantics properly
430             // handle the plausible entry set.
431             if (dir == forward) {
432                 for (auto vf = ait->second.begin(), vl = ait->second.end();
433                         vf != vl; ++vf) {
434                     plausibleNodes.erase(createNode(*vf));
435                 }
436                 
437             }
438             SliceFrame::ActiveMap::iterator del = ait;
439             ++ait;
440             cand.active.erase(del);
441         } else {
442             ++ait;
443         }
444         ++j;
445     }
446
447     for(unsigned i=0;i<matches.size();++i) {
448        // Check our predicates
449        if (p.widenAtPoint(matches[i].ptr)) {
450           widen(g, dir, matches[i]);
451        }
452        else if (p.endAtPoint(matches[i].ptr)) {
453           // Do nothing...
454        }
455        else {
456           cand.active[matches[i].reg].push_back(matches[i]);
457        }
458     }
459 //    updateAndLinkTime += clock() - t;
460 //    fprintf(stderr, "updateAndLink: %.3lf\n", (float)updateAndLinkTime / CLOCKS_PER_SEC);
461
462     return true;
463 }
464
465 // similar to updateAndLink, but this version only looks at the
466 // unified cache. it then inserts edges for matching elements.
467 void Slicer::updateAndLinkFromCache(
468     Graph::Ptr g,
469     Direction dir,
470     SliceFrame & f, 
471     DefCache & cache)
472 {
473     SliceFrame::ActiveMap::iterator ait = f.active.begin();
474
475     // if the abstract region of interest is in the defcache,
476     // update it and link it
477
478     for( ; ait != f.active.end(); ) {
479         AbsRegion const& r = (*ait).first;
480         if(!cache.defines(r)) {
481             ++ait;
482             continue;
483         }
484
485         // Link them up 
486         vector<Element> const& eles = (*ait).second;
487         set<Def> const& defs = cache.get(r);
488         set<Def>::const_iterator dit = defs.begin();
489         for( ; dit != defs.end(); ++dit) {
490             for(unsigned i=0;i<eles.size();++i) {
491                 // don't create self-loops on assignments
492                 if (eles[i].ptr != (*dit).ele.ptr)
493                     insertPair(g,dir,eles[i],(*dit).ele,(*dit).data);
494             }
495         }
496
497         // Stop caring about this region
498         SliceFrame::ActiveMap::iterator del = ait;
499         ++ait;
500         f.active.erase(del);
501     }
502 }
503
504 void
505 Slicer::cachePotential(
506     Direction dir,
507     Assignment::Ptr assn,
508     DefCache & cache)
509 {
510     if(dir == forward) {
511         vector<AbsRegion> const& inputs = assn->inputs();
512         for(unsigned i=0;i<inputs.size();++i) {
513             (void)cache.get(inputs[i]);
514         }
515     } else {
516         (void)cache.get(assn->out());
517     }
518 }
519
520 /*
521  * Compare the assignment `assn' to the abstract region `cur'
522  * and see whether they match, for the direction-appropriate
523  * definition of "match". If so, generate new slice elements
524  * and return them in the `match' vector, after linking them
525  * to the elements associated with the region `cur'.
526  * Return true if these exists at least a match.
527  */
528 bool
529 Slicer::findMatch(
530     Graph::Ptr g,
531     Direction dir,
532     SliceFrame const& cand,
533     AbsRegion const& reg,
534     Assignment::Ptr assn,
535     vector<Element> & matches,
536     DefCache& cache)
537 {
538     bool hadmatch = false;
539     if(dir == forward) {
540                 slicing_cerr << "\t\tComparing candidate assignment " << assn->format() << " to input region " << reg.format() << endl;
541         vector<AbsRegion> const& inputs = assn->inputs();
542         for(unsigned i=0;i<inputs.size();++i) {
543             if(reg.contains(inputs[i])) {
544                 hadmatch = true;    
545                                 slicing_cerr << "\t\t\t Match!" << endl;
546                 // Link the assignments associated with this
547                 // abstract region (may be > 1)
548                 Element ne(cand.loc.block,cand.loc.func,reg,assn);
549
550                 // Cache
551                 cache.get(reg).insert( Def(ne,inputs[i]) );
552                 
553                 vector<Element> const& eles = cand.active.find(reg)->second;
554                 for(unsigned j=0;j<eles.size();++j) {
555                     insertPair(g,dir,eles[j],ne,inputs[i]);
556
557                 }
558             }
559         }
560         if(hadmatch) {
561             // In this case, we are now interested in
562             // the outputs of the assignment
563             matches.push_back(
564                 Element(cand.loc.block,cand.loc.func,assn->out(),assn));
565         }
566     } else {
567         slicing_printf("\t\t\t\t\tComparing current %s to candidate %s\n",
568             reg.format().c_str(),assn->out().format().c_str());
569         if(reg.contains(assn->out())) {
570             hadmatch = true;
571             slicing_printf("\t\t\t\t\t\tMatch!\n");
572
573             // Link the assignments associated with this
574             // abstract region (may be > 1)
575             Element ne(cand.loc.block,cand.loc.func,reg,assn); 
576
577             // Cache
578             cache.get(reg).insert( Def(ne,reg) );
579             slicing_printf("\t\t\t cached [%s] -> <%s,%s>\n",
580                reg.format().c_str(),
581                 ne.ptr->format().c_str(),reg.format().c_str());
582
583             vector<Element> const& eles = cand.active.find(reg)->second;
584             for(unsigned i=0;i<eles.size();++i) {
585                 // N.B. using the AbsRegion from the Element, which
586                 //      may differ from the `reg' parameter to this
587                 //      method because of transformation though
588                 //      call or return edges. This `true' AbsRegion
589                 //      is used to associate two different AbsRegions
590                 //      during symbolic evaluation
591                 // if (eles[i].ptr != ne.ptr)
592                 if (eles[i].ptr->addr() != ne.ptr->addr())
593                     insertPair(g,dir,eles[i],ne,eles[i].reg);
594             }
595
596             // In this case, we are now interested in the 
597             // _inputs_ to the assignment
598             vector<AbsRegion> const& inputs = assn->inputs();
599             for(unsigned i=0; i< inputs.size(); ++i) {
600                 ne.reg = inputs[i];
601                 matches.push_back(ne);
602             }
603         }
604     }
605
606     return hadmatch;
607 }
608
609
610 bool 
611 Slicer::getNextCandidates(
612     Direction dir,
613     Predicates & p,
614     SliceFrame const& cand,
615     vector<SliceFrame> & newCands)
616 {
617     if(dir == forward) {
618         return getSuccessors(p,cand,newCands);
619     }
620     else {
621         return getPredecessors(p,cand,newCands);
622     }
623 }
624
625 /*
626  * Given the location (instruction) in `cand', find zero or more
627  * control flow successors from this location and create new slicing
628  * frames for them. Certain types of control flow require mutation of
629  * the SliceFrame (modification of context, e.g.) AND mutate the 
630  * abstract regions in the frame's `active' list (e.g. modifying
631  * stack locations).
632  */
633 bool
634 Slicer::getSuccessors(
635     Predicates &p,
636     SliceFrame const& cand,
637     vector<SliceFrame> & newCands)
638 {
639     InsnVec::iterator next = cand.loc.current;
640     ++next;
641
642     // Case 1: just one intra-block successor
643     if(next != cand.loc.end) {
644         SliceFrame nf = cand;
645         nf.loc.current = next;
646         assert(nf.loc.block);
647         newCands.push_back(nf);
648
649         slicing_printf("\t\t\t\t added intra-block successor\n");
650         return true;
651     }
652
653     // Case 2: end of the block. Subcases are calls, returns, and other
654     bool err = false;
655
656     if(containsCall(cand.loc.block)) {
657         slicing_printf("\t\t Handling call... ");
658         SliceFrame nf = cand;
659
660         // nf may be transformed
661         if(handleCall(p,nf,err)) {
662             slicing_printf("success, err: %d\n",err);
663             assert(nf.loc.block);
664             newCands.push_back(nf);
665         } else {
666             slicing_printf("failed, err: %d\n",err);
667         }
668     }
669     else if(containsRet(cand.loc.block)) {
670         slicing_printf("\t\t Handling return... ");
671         SliceFrame nf = cand;
672     
673         // nf may be transformed
674         if(handleReturn(p,nf,err)) {
675             slicing_printf("success, err: %d\n",err);
676             assert(nf.loc.block);
677             newCands.push_back(nf);
678         } else {
679             slicing_printf("failed, err: %d\n",err);
680         }
681     }
682     else {
683         // Default intraprocedural control flow case; this
684         // case may produce multiple new frames, but it
685         // will not transform any of them (besides changing
686         // the location)
687
688         const Block::edgelist & targets = cand.loc.block->targets();
689         Block::edgelist::const_iterator eit = targets.begin();
690         for( ; eit != targets.end(); ++eit) {
691             if((*eit)->sinkEdge()) {
692                 // will force widening
693                 newCands.push_back(SliceFrame(false));
694             } 
695             else {
696                 SliceFrame nf = cand;
697                 slicing_printf("\t\t Handling default edge type %d... ",
698                     (*eit)->type());
699                 if(handleDefault(forward,p,*eit,nf,err)) {
700                     slicing_printf("success, err: %d\n",err);
701                     assert(nf.loc.block);
702                     newCands.push_back(nf);
703                 } else {
704                     slicing_printf("failed, err: %d\n",err);
705                 }
706             }
707         }
708     }
709     return !err;
710 }
711
712 void Slicer::handlePredecessorEdge(ParseAPI::Edge* e,
713                                    Predicates& p,
714                                    SliceFrame const& cand,
715                                    vector<SliceFrame> & newCands,
716                                    bool& err,
717                                    SliceFrame& nf)
718 {
719   visitedEdges.insert(e);
720   switch(e->type()) 
721   {
722   case CALL:
723     slicing_printf("\t\t Handling call... ");
724     if(handleCallBackward(p,cand,newCands,e,err)) {
725       slicing_printf("succeess, err: %d\n",err);
726     } else {
727       slicing_printf("failed, err: %d\n",err);
728     }
729     break;
730   case RET:
731     slicing_printf("\t\t Handling return... ");
732     nf = cand;
733     if(handleReturnBackward(p,cand,nf,e,err)) {
734       slicing_printf("succeess, err: %d\n",err);
735     } else {
736       slicing_printf("failed, err: %d\n",err);
737     }
738     break;
739   default:
740     nf = cand;
741     slicing_printf("\t\t Handling default edge type %d... ",
742                    e->type());
743     if(handleDefault(backward,p,e,nf,err)) {
744       slicing_printf("success, err: %d\n",err);
745       newCands.push_back(nf);
746     } else {
747       slicing_printf("failed, err: %d\n",err);
748     }
749   }
750 }
751
752
753   
754
755 /*
756  * Same as successors, only backwards
757  */
758 bool
759 Slicer::getPredecessors(
760     Predicates &p,
761     SliceFrame const& cand,
762     vector<SliceFrame> & newCands)
763 {
764     static clock_t getPredecessorsIntraTime = 0, 
765                    getPredecessorsInterTime = 0,
766                    t;
767 //    t = clock();
768     InsnVec::reverse_iterator prev = cand.loc.rcurrent;
769     ++prev;
770
771     // Case 1: intra-block
772     if(prev != cand.loc.rend) {
773         SliceFrame nf(cand.loc,cand.con, cand.firstCond);
774         nf.loc.rcurrent = prev;
775
776         // Slightly more complicated than the forward case; check
777         // a predicate for each active abstract region to see whether
778         // we should continue
779         bool cont = false;
780         SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
781         for( ; ait != cand.active.end(); ++ait) {
782             bool add = p.addPredecessor((*ait).first);
783             if(add)
784                 nf.active.insert(*ait);
785             cont = cont || add;
786         }
787
788         if(cont) {
789             slicing_printf("\t\t\t\t Adding intra-block predecessor %lx\n",
790                 nf.loc.addr());
791             slicing_printf("\t\t\t\t Current regions are:\n");
792             if(slicing_debug_on()) {
793                 SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
794                 for( ; ait != cand.active.end(); ++ait) {
795                     slicing_printf("\t\t\t\t%s\n",
796                         (*ait).first.format().c_str());
797
798                         vector<Element> const& eles = (*ait).second;
799                         for(unsigned i=0;i<eles.size();++i) {
800                                 slicing_printf("\t\t\t\t\t [%s] : %s\n",
801                                         eles[i].reg.format().c_str(),eles[i].ptr->format().c_str());
802                         }
803                 }
804             }
805     
806             newCands.push_back(nf);
807         }
808 //      getPredecessorsIntraTime += clock() - t;
809 //      fprintf(stderr, "getPredecessors (intra): %.3lf\n", (float)getPredecessorsIntraTime / CLOCKS_PER_SEC);
810         return true;
811     }
812
813     // Case 2: inter-block
814     bool err = false;
815     SliceFrame nf;
816     
817     SingleContextOrInterproc epred(cand.loc.func, true, true);
818
819     const Block::edgelist & sources = cand.loc.block->sources();
820     std::for_each(boost::make_filter_iterator(epred, sources.begin(), sources.end()),
821                   boost::make_filter_iterator(epred, sources.end(), sources.end()),
822                   boost::bind<void>(&Slicer::handlePredecessorEdge,
823                                     this,
824                                     _1,
825                                     boost::ref(p),
826                                     boost::ref(cand),
827                                     boost::ref(newCands),
828                                     boost::ref(err),
829                                     boost::ref(nf)
830                                     ));
831 //    getPredecessorsInterTime += clock() - t;
832 //    fprintf(stderr, "getPredecessors (inter): %.3lf\n", (float)getPredecessorsInterTime / CLOCKS_PER_SEC);
833
834     return !err; 
835 }
836
837 /*
838  * Process a call instruction, determining whether to follow the
839  * call edge (with the help of the predicates) or the fallthrough
840  * edge (coloquially referred to as `funlink' thanks to our 
841  * departed Arizona alum --- much respect M.L.)
842  */
843 bool
844 Slicer::handleCall(
845     Predicates & p,
846     SliceFrame & cur,
847     bool & err)
848 {
849     ParseAPI::Block * callee = NULL;
850     ParseAPI::Edge * funlink = NULL;
851     bool widen = false;
852
853     const Block::edgelist & targets = cur.loc.block->targets();
854     Block::edgelist::const_iterator eit = targets.begin();
855     for( ; eit != targets.end(); ++eit) {
856         ParseAPI::Edge * e = *eit;
857         if (e->sinkEdge()) widen = true;
858         else if(e->type() == CALL) {
859             if (callee && callee != e->trg()) {
860                 // Oops
861                 widen = true;
862             }
863             callee = e->trg();
864         } else if(e->type() == CALL_FT) {
865            funlink = e;
866         }
867     }
868     
869     if(followCall(p, callee, cur)) {
870        if (widen) {
871           // Indirect call that they wanted us to follow, so widen.
872           err = true;
873           return true;
874        }
875
876        ParseAPI::Block * caller_block = cur.loc.block;
877        
878        cur.loc.block = callee;
879        cur.loc.func = getEntryFunc(callee);
880        getInsns(cur.loc);
881        
882        // Update the context of the slicing frame
883        // and modify the abstract regions in its
884        // active vector
885        if(!handleCallDetails(cur,caller_block)) {
886           err = true;
887           return false;
888        }
889     }
890     else {
891         // Use the funlink
892         if(!funlink) {
893             // FIXME I am preserving a comment and semantics that
894             // I do not understand here, again as of 06697df. Quote:
895
896             // ???
897             return false;
898         }
899         if(!handleDefault(forward,p,funlink,cur,err)) {
900             err = true;
901             return false;
902         }
903     }
904     return true;
905 }
906
907 /*
908  * Builds up a call stack and callee function, and ask
909  * the predicate whether we should follow the call (or,
910  * implicitly, follow its fallthrough edge instead).
911  */
912 bool
913 Slicer::followCall(
914     Predicates & p,
915     ParseAPI::Block * target,
916     SliceFrame & cur)
917 {
918     // FIXME quote:
919    // A NULL callee indicates an indirect call.
920    // TODO on that one...
921    
922     ParseAPI::Function * callee = (target ? getEntryFunc(target) : NULL);
923     
924     // cons up a call stack
925     stack< pair<ParseAPI::Function *, int> > callStack;
926     for(Context::reverse_iterator calls = cur.con.rbegin();
927         calls != cur.con.rend(); ++calls)
928     {
929         if(NULL != calls->func) {
930             callStack.push(make_pair(calls->func,calls->stackDepth));
931         }
932     } 
933     // Quote:
934         // FIXME: assuming that this is not a PLT function, since I have no
935         // idea at present.  -- BW, April 2010
936
937     // Give the predicate an opportunity to accept this call for each
938     // of the abstract regions in the active set
939     //
940     // XXX There is an interesting concern here. What if the predicate
941     // would indicate `follow' for one active AbsRegion and `do not
942     // follow' for another? What you'd want to do in that case is
943     // fork into multiple SliceFrames for absregions that should go
944     // one way or the other. This is something that could be done by
945     // moving the handleCallDetails() call into this method and
946     // modifying the nextCands vector here, as opposed to in
947     // handleCall(). 
948     // 
949     // This issue needs review by a person involved in slicer design.
950     // FIXME
951
952     bool ret = false;
953
954     SliceFrame::ActiveMap::iterator ait = cur.active.begin();
955     for( ; ait != cur.active.end(); ++ait) {
956         ret = ret || p.followCall(callee, callStack, (*ait).first);
957     }
958     
959     return ret;
960 }
961
962 void 
963 Slicer::shiftAllAbsRegions(
964     SliceFrame & cur,
965     long stack_depth,
966     ParseAPI::Function *callee)
967 {
968     SliceFrame::ActiveMap newMap;
969
970     // fix all of the abstract regions
971     SliceFrame::ActiveMap::iterator ait = cur.active.begin();
972     for( ; ait != cur.active.end(); ++ait) {
973         AbsRegion const& reg = (*ait).first;
974
975         // shortcut -- do nothing if no adjustment is necessary
976         if(reg.absloc() == Absloc()) {
977             // N.B. doing this the hard way (rather than map.insert()
978             //      in case a previous or later iteration transforms
979             //      a different AbsRegion to the same as (*ait).first
980             vector<Element> & e = newMap[(*ait).first];
981             e.insert(e.end(),(*ait).second.begin(),(*ait).second.end());
982             continue;
983         }
984
985         // Adjust the mapping region, but do not adjust the regions of the
986         // elements --- these are maintained to their old values for
987         // annotating the slicing graph edges to facilitate substitution
988         // in symbolic expansion
989         AbsRegion newReg;
990         shiftAbsRegion(reg,newReg,stack_depth,callee);
991
992         // just copy the elements
993         vector<Element> & e = newMap[newReg];
994         e.insert(e.end(),(*ait).second.begin(),(*ait).second.end());
995     }
996     // and replace
997     cur.active = newMap;    
998 }
999
1000 /*
1001  * Adjust the slice frame's context and translates the abstract
1002  * regions in the active list from caller to callee
1003  */
1004 bool
1005 Slicer::handleCallDetails(
1006     SliceFrame & cur,
1007     ParseAPI::Block * caller_block)
1008
1009     ParseAPI::Function * caller = cur.con.front().func;
1010     ParseAPI::Function * callee = cur.loc.func;
1011
1012     long stack_depth = 0;
1013     if(!getStackDepth(caller, caller_block, caller_block->end(), stack_depth))
1014         return false;
1015
1016     // Increment the context
1017     pushContext(cur.con, callee, caller_block, stack_depth);
1018
1019     // Transform the active abstract regions
1020     shiftAllAbsRegions(cur,stack_depth,callee);
1021
1022     return true;
1023 }
1024
1025 /*
1026  * Properly adjusts the location & context of the slice frame and the
1027  * AbsRegions of its active elements
1028  */
1029 bool 
1030 Slicer::handleReturn(
1031     Predicates & /* p */,
1032     SliceFrame & cur,
1033     bool & err)
1034 {
1035     // Sanity check -- when we pop (in handleReturnDetails),
1036     // it should not result in context being empty
1037     //
1038     // FIXME I duplicated this from the old version; I don't
1039     //       understand why this doesn't set err = false.
1040     if(cur.con.size() <= 1)
1041         return false;
1042
1043     // Find successor
1044     ParseAPI::Block * retBlock = NULL;
1045     
1046     const Block::edgelist & targets = cur.loc.block->targets();
1047     Block::edgelist::const_iterator eit = targets.begin();
1048     for(; eit != targets.end(); ++eit) {
1049         if((*eit)->type() == CALL_FT) {
1050             retBlock = (*eit)->trg();
1051             if ((*eit)->sinkEdge()) {
1052                 cerr << "Weird!" << endl;
1053             }
1054             break;
1055         }
1056     }
1057     if(!retBlock) {
1058         err = true;
1059         return false;
1060     }
1061
1062     // Pops a context and adjusts the abstract regions in `active'
1063     handleReturnDetails(cur);
1064
1065     // Fix location given new context
1066     cur.loc.func = cur.con.front().func;
1067     cur.loc.block = retBlock;
1068     getInsns(cur.loc);
1069
1070     return true;
1071 }
1072
1073 /*
1074  * Do the actual context popping and active AbsRegion translation
1075  */
1076 void
1077 Slicer::handleReturnDetails(
1078     SliceFrame & cur)
1079 {
1080     long stack_depth = cur.con.front().stackDepth;
1081     popContext(cur.con);
1082
1083     assert(!cur.con.empty());
1084
1085     slicing_printf("\t%s, \n",
1086         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1087         cur.con.front().stackDepth);
1088
1089     // Transform the active abstract regions
1090     shiftAllAbsRegions(cur,-1*stack_depth,cur.con.front().func);
1091 }
1092
1093 static bool IsEqualCondJump(ParseAPI::Block *b) {
1094     InstructionAPI::Instruction::Ptr insn = b->getInsn(b->last());
1095     entryID id = insn->getOperation().getID();
1096     if (id == e_jz || id == e_jnz) return true;
1097     return false;
1098 }
1099
1100 static bool EndsWithConditionalJump(ParseAPI::Block *b) {
1101     bool cond = false;
1102 //    if (IsEqualCondJump(b)) return false;
1103     for (auto eit = b->targets().begin(); eit != b->targets().end(); ++eit)
1104         if ((*eit)->type() == COND_TAKEN) cond = true;
1105     return cond;
1106 }
1107
1108 static void DFS(ParseAPI::Block *cur, set<ParseAPI::Block*> &visit, ParseAPI::Edge *ban, set<ParseAPI::Block*> &targets) {
1109     if (visit.find(cur) != visit.end()) return;    
1110     visit.insert(cur);
1111     targets.erase(cur);
1112     if (targets.empty()) return;
1113     for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit)
1114         if ((*eit) != ban && (*eit)->type() != CALL && (*eit)->type() != RET)
1115             DFS((*eit)->trg(), visit, ban, targets);
1116 }
1117 bool Slicer::ReachableFromBothBranches(ParseAPI::Edge *e, vector<Element> &newE) {
1118     static clock_t t1 = 0, t2;
1119 //    t2 = clock();
1120
1121     ParseAPI::Block *start;
1122     start = e->src();
1123     set<ParseAPI::Block*> visited , targets;
1124     for (auto eit = newE.begin(); eit != newE.end(); ++eit)
1125         targets.insert(eit->block);
1126     DFS(start, visited, e, targets);
1127 //    t1 += clock() - t2;
1128 //    fprintf(stderr, "check control flow dependency %.3lf\n", (float)t1 / CLOCKS_PER_SEC);
1129 //    fprintf(stderr, "%d %d\n", visited.size(), targets.size());
1130     return targets.empty();
1131 }
1132
1133
1134 bool
1135 Slicer::handleDefault(
1136     Direction dir,
1137     Predicates & p,
1138     ParseAPI::Edge * e,
1139     SliceFrame & cur,
1140     bool & /* err */)
1141 {
1142     if(dir == forward) {
1143         cur.loc.block = e->trg();
1144         getInsns(cur.loc);
1145     } else {
1146         cur.loc.block = e->src();
1147         getInsnsBackward(cur.loc);
1148         if ((true || cur.firstCond) && EndsWithConditionalJump(e->src())) {
1149             vector<Element> newE;        
1150             
1151             for (auto ait = cur.active.begin(); ait != cur.active.end(); ++ait) {               
1152                 newE.insert(newE.end(), ait->second.begin(), ait->second.end());
1153             }       
1154 /*
1155             for (auto ait = cur.active.begin(); ait != cur.active.end(); ++ait) {
1156                 vector<Element> & oldE = ait->second; 
1157                 for (auto oit = oldE.begin(); oit != oldE.end(); ++oit)
1158                     if (!f_->postDominates(oit->block, cur.loc.block)) newE.push_back(*oit);
1159             }
1160 */          
1161 //          if (!ReachableFromBothBranches(e, newE)) {
1162 //            if (!newE.empty()) {    
1163             if (p.searchForControlFlowDep()) {
1164                 if (cur.loc.block->obj()->cs()->getAddressWidth() == 8)
1165                     cur.active[AbsRegion(Absloc(x86_64::rip))] = newE;
1166                 else if  (cur.loc.block->obj()->cs()->getAddressWidth() == 4)
1167                     cur.active[AbsRegion(Absloc(x86::eip))] = newE;
1168             }
1169
1170             cur.firstCond = false;
1171             slicing_printf("\tadding tracking ip for control flow information ");
1172         }
1173     }
1174     return true;
1175 }
1176
1177 /* ----------------- backwards slicing implementations ------------------ */
1178
1179 bool
1180 Slicer::handleCallBackward(
1181     Predicates & p,
1182     SliceFrame const& cand,
1183     vector<SliceFrame> & newCands,
1184     ParseAPI::Edge * e,
1185     bool & /* err */)
1186 {
1187     // We don't know which function the caller block belongs to,
1188     // so check each possibility against the predicate.
1189     //
1190     // XXX   this suffers the same problem as followCall in the forward
1191     //       case; the predicates test against only a single abstract
1192     //       region. What we do here is to build up mappings from
1193     //       function paths (that will be followed) to sets of abstract
1194     //       regions, then create SliceFrames with these sets.
1195
1196     map<ParseAPI::Function *, SliceFrame::ActiveMap > fmap;
1197
1198     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1199     for( ; ait != cand.active.end(); ++ait) {
1200         vector<ParseAPI::Function *> follow = 
1201             followCallBackward(p,cand,(*ait).first,e->src());
1202         for(unsigned j=0;j<follow.size();++j) {
1203             fmap[follow[j]].insert(*ait);
1204         }
1205     }
1206
1207     map<ParseAPI::Function *, SliceFrame::ActiveMap >::iterator mit = 
1208         fmap.begin();
1209     for( ; mit != fmap.end(); ++mit) {
1210         ParseAPI::Function * f = (*mit).first;
1211         SliceFrame::ActiveMap & act = (*mit).second;
1212     
1213         SliceFrame nf(cand.loc,cand.con, cand.firstCond);
1214         nf.active = act;
1215
1216         nf.con.push_back(ContextElement(f));
1217         nf.loc.block = e->src();
1218         nf.loc.func = f;
1219
1220         // pop context & adjust AbsRegions
1221         if(!handleCallDetailsBackward(nf)) {
1222             // FIXME I have preserved this behavior (returning false if
1223             //       the current frame can't be adjusted). It seems to
1224             //       me that we ought to set err = true and continue
1225             //       processing the rest of the call edges.
1226             //
1227             //       This issue needs review by somebody knowledgeable
1228             //       about the slicer.
1229             return false;
1230         }
1231
1232         getInsnsBackward(nf.loc);
1233         newCands.push_back(nf);
1234     } 
1235     return true;
1236 }
1237
1238 /*
1239  * FIXME egregious copying
1240  */
1241 vector<ParseAPI::Function *>
1242 Slicer::followCallBackward(
1243     Predicates & p,
1244     SliceFrame const& cand,
1245     AbsRegion const& reg,
1246     ParseAPI::Block * caller_block)
1247 {
1248     stack< pair<ParseAPI::Function *, int> > callStack;  
1249     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1250         calls != cand.con.rend(); ++calls)
1251     {
1252         if(calls->func) {
1253             callStack.push(
1254                std::make_pair(calls->func, calls->stackDepth));
1255         }
1256     }
1257     return p.followCallBackward(caller_block, callStack, reg);
1258 }
1259
1260 bool
1261 Slicer::handleCallDetailsBackward(
1262     SliceFrame & cur)
1263 {
1264     ParseAPI::Block * callBlock = cur.loc.block;
1265     ParseAPI::Function * caller = cur.loc.func;
1266
1267     Address callBlockLastInsn = callBlock->lastInsnAddr();
1268
1269     long stack_depth;
1270     if(!getStackDepth(caller, callBlock, callBlockLastInsn,stack_depth)) {
1271         return false;
1272     }
1273
1274     popContext(cur.con);
1275     assert(!cur.con.empty());
1276
1277
1278     slicing_printf("\t%s, %d\n",
1279         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1280         cur.con.front().stackDepth);
1281
1282     // Transform the active abstract regions
1283     shiftAllAbsRegions(cur,-1*stack_depth,caller);
1284
1285     return true;
1286 }
1287     
1288 bool
1289 Slicer::handleReturnBackward(
1290     Predicates & p,
1291     SliceFrame const& cand,
1292     SliceFrame & newCand,
1293     ParseAPI::Edge * e,
1294     bool & err)
1295 {
1296     ParseAPI::Block * callee = e->src();
1297
1298     // cons up a call stack for the call associated
1299     // with this return and ask the predicates whether
1300     // they would have come down this call.
1301     //
1302     // FIXME the issue of predicates evaluating only a
1303     //       single abstract region applies here as well;
1304     //       see comments in handleCall and handleCallBackward
1305
1306     if(followReturn(p,cand,callee)) {
1307         // XXX it is not clear to me why a null callee is an error here
1308         //     but not if followReturn returns false FIXME
1309         if(!callee) {
1310             err = true;
1311             return false;
1312         }
1313
1314         newCand = cand;
1315         newCand.loc.block = callee;
1316         newCand.loc.func = getEntryFunc(callee);
1317         getInsnsBackward(newCand.loc);
1318
1319         if(!handleReturnDetailsBackward(newCand,cand.loc.block)) {
1320             err = true;
1321             return false;
1322         }
1323         return true;
1324     } 
1325     return false;
1326 }
1327
1328 bool
1329 Slicer::handleReturnDetailsBackward(
1330     SliceFrame & cur,
1331     ParseAPI::Block * caller_block)
1332 {
1333     ParseAPI::Function * caller = cur.con.front().func;
1334     ParseAPI::Function * callee = cur.loc.func;
1335
1336     long stack_depth;
1337     if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
1338         return false;
1339     }
1340     
1341     pushContext(cur.con, callee, caller_block, stack_depth);
1342
1343     // Transform the active abstract regions
1344     shiftAllAbsRegions(cur,stack_depth,caller);
1345
1346     return true; 
1347 }
1348
1349 bool
1350 Slicer::followReturn(
1351     Predicates & p,
1352     SliceFrame const& cand,
1353     ParseAPI::Block * source)
1354 {
1355     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1356     
1357     stack< pair<ParseAPI::Function *, int> > callStack;
1358     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1359         calls != cand.con.rend(); ++calls)
1360     {
1361         if(calls->func) {
1362             callStack.push(
1363                std::make_pair(calls->func, calls->stackDepth));
1364         }
1365     }
1366
1367     bool ret = false;
1368     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1369     for( ; ait != cand.active.end(); ++ait) {
1370         ret = ret || p.followCall(callee,callStack,(*ait).first);
1371     }
1372     return ret;
1373 }
1374     
1375
1376
1377 /* ------------------------------------------- */
1378
1379 Address SliceNode::addr() const { 
1380   if (a_)
1381     return a_->addr();
1382   return 0;
1383 }
1384
1385 bool containsCall(ParseAPI::Block *block) {
1386   // We contain a call if the out-edges include
1387   // either a CALL or a CALL_FT edge
1388   const Block::edgelist &targets = block->targets();
1389   Block::edgelist::const_iterator eit = targets.begin();
1390   for (; eit != targets.end(); ++eit) {
1391     ParseAPI::Edge *edge = *eit;
1392     if (edge->type() == CALL) return true;
1393   }
1394   return false;
1395 }
1396
1397 bool containsRet(ParseAPI::Block *block) {
1398   // We contain a call if the out-edges include
1399   // either a CALL or a CALL_FT edge
1400   const Block::edgelist &targets = block->targets();
1401   Block::edgelist::const_iterator eit = targets.begin();
1402   for (; eit != targets.end(); ++eit) {
1403     ParseAPI::Edge *edge = *eit;
1404     if (edge->type() == RET) return true;
1405   }
1406   return false;
1407 }
1408
1409 static void getInsnInstances(ParseAPI::Block *block,
1410                       Slicer::InsnVec &insns) {
1411   Offset off = block->start();
1412   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
1413   if (ptr == NULL) return;
1414   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
1415   while (off < block->end()) {
1416     insns.push_back(std::make_pair(d.decode(), off));
1417     off += insns.back().first->size();
1418   }
1419 }
1420
1421 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
1422   return block->obj()->findFuncByEntry(block->region(), block->start());
1423 }
1424
1425 // Constructor. Takes the initial point we slice from. 
1426
1427 // TODO: make this function-less interprocedural. That would throw the
1428 // stack analysis for a loop, but is generally doable...
1429 Slicer::Slicer(Assignment::Ptr a,
1430                ParseAPI::Block *block,
1431                ParseAPI::Function *func,
1432                bool cache,
1433                bool stackAnalysis) : 
1434   a_(a),
1435   b_(block),
1436   f_(func),
1437   // Xiaozhu: Temporarily disable stackanalysis, should be able to
1438   // specify it 
1439   converter(cache, stackAnalysis) {
1440   df_init_debug();
1441 };
1442
1443 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
1444
1445         // delete cache state
1446   unique_edges_.clear(); 
1447
1448   return sliceInternal(forward, predicates);
1449 }
1450
1451 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
1452   // delete cache state
1453   unique_edges_.clear(); 
1454
1455   return sliceInternal(backward, predicates);
1456 }
1457
1458 bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
1459   StackAnalysis sA(func);
1460
1461   StackAnalysis::Height heightSA = sA.findSP(block, callAddr);
1462
1463   // Ensure that analysis has been performed.
1464
1465   assert(!heightSA.isTop());
1466   
1467   if (heightSA.isBottom()) {
1468     return false;
1469   }
1470   
1471   height = heightSA.height();
1472   
1473   // The height will include the effects of the call
1474   // Should check the region... 
1475
1476   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
1477   //<< std::dec << " " << (int) height << endl;
1478
1479   return true;
1480 }
1481
1482 void Slicer::pushContext(Context &context,
1483                          ParseAPI::Function *callee,
1484                          ParseAPI::Block *callBlock,
1485                          long stackDepth) {
1486   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
1487   assert(context.front().block == NULL);
1488   context.front().block = callBlock;
1489
1490   slicing_cerr << "\t" 
1491                << (context.front().func ? context.front().func->name() : "NULL")
1492                << ", " 
1493                << context.front().stackDepth 
1494                << endl;
1495
1496     context.push_front(ContextElement(callee, stackDepth));
1497 };
1498
1499 void Slicer::popContext(Context &context) {
1500   context.pop_front();
1501
1502   context.front().block = NULL;
1503 }
1504
1505 void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
1506                             AbsRegion &calleeReg,
1507                             long stack_depth,
1508                             ParseAPI::Function *callee) {
1509   if (callerReg.absloc() == Absloc()) {
1510     // Typed, so just keep the same type and call it a day
1511     calleeReg = callerReg;
1512     return;
1513   }
1514   else {
1515     assert(callerReg.type() == Absloc::Unknown);
1516     
1517     const Absloc &callerAloc = callerReg.absloc();
1518     if (callerAloc.type() != Absloc::Stack) {
1519       calleeReg = AbsRegion(callerAloc);
1520     }
1521     else {
1522       if (stack_depth == -1) {
1523         // Oops
1524         calleeReg = AbsRegion(Absloc::Stack);
1525         return;
1526       }
1527       else {
1528         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
1529         //<< " by stack depth " << stack_depth 
1530         //<< " and setting to function " << callee->name() << endl;
1531         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
1532                                      0, // Entry point has region 0 by definition
1533                                      callee));
1534       }
1535     }
1536   }
1537 }
1538
1539 bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
1540   // Did we find a definition of the same abstract region?
1541   // TBD: overlaps ins't quite the right thing here. "contained
1542   // by" would be better, but we need to get the AND/OR
1543   // of abslocs hammered out.
1544   
1545   if (assign->out().type() != Absloc::Unknown) {
1546     // A region assignment can never kill
1547     return false; 
1548   }
1549
1550   if (assign->insn()->getOperation().getID() == e_call && reg.absloc().type() == Absloc::Register) {
1551       MachRegister r = reg.absloc().reg();
1552       ABI* abi = ABI::getABI(b_->obj()->cs()->getAddressWidth());
1553       int index = abi->getIndex(r);
1554       if (index >= 0)
1555           if (abi->getCallWrittenRegisters()[abi->getIndex(r)]) return true;
1556   }
1557   return reg.contains(assign->out());
1558 }
1559
1560 // creates a new node from an element if that node does not yet exist.
1561 // otherwise, it returns the pre-existing node.
1562 SliceNode::Ptr Slicer::createNode(Element const&elem) {
1563   if (created_.find(elem.ptr) != created_.end()) {
1564     return created_[elem.ptr];
1565   }
1566   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
1567   created_[elem.ptr] = newNode;
1568
1569   // mark this node as plausibly being entry/exit.
1570   plausibleNodes.insert(newNode); 
1571   return newNode;
1572 }
1573
1574 std::string SliceNode::format() const {
1575   if (!a_) {
1576     return "<NULL>";
1577   }
1578
1579   stringstream ret;
1580   ret << "(" << a_->format() << "@" <<
1581     f_->name() << ")";
1582   return ret.str();
1583 }
1584
1585 // converts an instruction to a vector of assignments. if this slicer has
1586 // already converted this instruction, this function returns the same
1587 // assignments.
1588 // Note that we CANNOT use a global cache based on the address
1589 // of the instruction to convert because the block that contains
1590 // the instructino may change during parsing.
1591 void Slicer::convertInstruction(Instruction::Ptr insn,
1592                                 Address addr,
1593                                 ParseAPI::Function *func,
1594                                 ParseAPI::Block *block,
1595                                 std::vector<Assignment::Ptr> &ret) {
1596   converter.convert(insn,
1597                     addr,
1598                     func,
1599                     block,
1600                     ret);
1601   return;
1602 }
1603
1604 void Slicer::getInsns(Location &loc) {
1605
1606
1607   InsnCache::iterator iter = insnCache_.find(loc.block);
1608   if (iter == insnCache_.end()) {
1609     getInsnInstances(loc.block, insnCache_[loc.block]);
1610   }
1611   
1612   loc.current = insnCache_[loc.block].begin();
1613   loc.end = insnCache_[loc.block].end();
1614 }
1615
1616 void Slicer::getInsnsBackward(Location &loc) {
1617     assert(loc.block->start() != (Address) -1); 
1618     InsnCache::iterator iter = insnCache_.find(loc.block);
1619     if (iter == insnCache_.end()) {
1620       getInsnInstances(loc.block, insnCache_[loc.block]);
1621     }
1622
1623     loc.rcurrent = insnCache_[loc.block].rbegin();
1624     loc.rend = insnCache_[loc.block].rend();
1625 }
1626
1627 // inserts an edge from source to target (forward) or target to source
1628 // (backward) if the edge does not yet exist. this is done by converting
1629 // source and target to graph nodes (creating them if they do not exist).
1630 void Slicer::insertPair(Graph::Ptr ret,
1631                         Direction dir,
1632                         Element const&source,
1633                         Element const&target,
1634                         AbsRegion const& data) 
1635 {
1636     SliceNode::Ptr s = createNode(source);
1637     SliceNode::Ptr t = createNode(target);
1638
1639     insertPair(ret, dir, s, t, data);
1640 }
1641
1642 // inserts an edge from source to target (forward) or target to source
1643 // (backward) if the edge does not yet exist.
1644 void Slicer::insertPair(Graph::Ptr ret,
1645                         Direction dir,
1646                         SliceNode::Ptr& s,
1647                         SliceNode::Ptr& t,
1648                         AbsRegion const& data) 
1649 {
1650
1651   EdgeTuple et(s,t,data);
1652   if(unique_edges_.find(et) != unique_edges_.end()) {
1653     unique_edges_[et] += 1;
1654     return;
1655   }
1656   unique_edges_[et] = 1;  
1657
1658   if (dir == forward) {
1659      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1660      ret->insertPair(s, t, e);
1661
1662      // this node is clearly not entry/exit.
1663      plausibleNodes.erase(s);
1664   } else {
1665      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1666      ret->insertPair(t, s, e);
1667
1668      // this node is clearly not entry/exit.
1669      plausibleNodes.erase(s); 
1670   }
1671 }
1672
1673 void
1674 Slicer::widenAll(
1675     Graph::Ptr g,
1676     Direction dir,
1677     SliceFrame const& cand)
1678 {
1679     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1680     for( ; ait != cand.active.end(); ++ait) {
1681         vector<Element> const& eles = (*ait).second;
1682         for(unsigned i=0;i<eles.size();++i)
1683             widen(g,dir,eles[i]);
1684     }
1685 }
1686
1687 void Slicer::widen(Graph::Ptr ret,
1688                    Direction dir,
1689                    Element const&e) {
1690   if (dir == forward) {
1691     ret->insertPair(createNode(e),
1692                     widenNode());
1693     ret->insertExitNode(widenNode());
1694   }
1695   else {
1696     ret->insertPair(widenNode(), createNode(e));
1697     ret->insertEntryNode(widenNode());
1698   }
1699 }
1700
1701 SliceNode::Ptr Slicer::widenNode() {
1702   if (widen_) {
1703     return widen_;
1704   }
1705
1706   widen_ = SliceNode::create(Assignment::Ptr(),
1707                               NULL, NULL);
1708   return widen_;
1709 }
1710
1711 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1712   if (dir == forward) {    
1713     ret->insertExitNode(createNode(e));
1714   }
1715   else {
1716     ret->insertEntryNode(createNode(e));
1717   }
1718 }
1719
1720 void Slicer::fastForward(Location &loc, Address
1721                          addr) {
1722   while ((loc.current != loc.end) &&
1723          (loc.addr() < addr)) {
1724     loc.current++;
1725   }
1726   assert(loc.current != loc.end);
1727   assert(loc.addr() == addr);
1728 }
1729
1730 void Slicer::fastBackward(Location &loc, Address addr) {
1731     while ((loc.rcurrent != loc.rend) &&
1732          (loc.addr() > addr)) {
1733     loc.rcurrent++;
1734   }
1735   assert(loc.rcurrent != loc.rend);
1736   assert(loc.addr() == addr);  
1737 }
1738
1739 // removes unnecessary nodes from the slice graph. this is
1740 // currently mostly ia32/amd64 flags that are written but
1741 // never read. 
1742 void Slicer::cleanGraph(Graph::Ptr ret) {
1743   slicing_cerr << "Cleaning up the graph..." << endl;
1744   // Clean the graph up
1745   
1746   // TODO: make this more efficient by backwards traversing.
1747   // For now, I know that we're generating graphs with tons of
1748   // unnecessary flag sets (which are immediately killed) and so
1749   // we don't have long non-exiting chains, we have "fuzz"
1750   
1751   NodeIterator nbegin, nend;
1752   ret->allNodes(nbegin, nend);
1753   
1754   std::list<Node::Ptr> toDelete;
1755   unsigned numNodes = 0;
1756   for (; nbegin != nend; ++nbegin) {
1757           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1758       numNodes++;
1759       SliceNode::Ptr foozle =
1760           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1761       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1762       if ((*nbegin)->hasOutEdges()) {
1763           slicing_cerr << "\t has out edges, leaving in" << endl;
1764           continue;
1765       }
1766
1767       // don't remove entry/exit nodes.
1768       if (ret->isEntryNode(*nbegin) || ret->isExitNode(*nbegin)) {
1769           continue;
1770       }
1771
1772       // mark non-flags nodes as exit nodes. these nodes are likely
1773       // relevant to the slice and should not be deleted. only delete 
1774       // flag nodes. this should stop the over-deleting by this
1775       // function, but this is a fairly ugly way of doing it. 
1776       const Absloc& abs = foozle->a_->out().absloc();
1777       if (abs.type() == Absloc::Register && 
1778                         (abs.reg().getArchitecture() == Arch_x86 
1779                          || abs.reg().getArchitecture() == Arch_x86_64) && 
1780                         (abs.reg().getBaseRegister() & x86::FLAG) == x86::FLAG) {
1781           slicing_cerr << "\t deleting" << endl;
1782           toDelete.push_back(*nbegin);
1783       } else {
1784           ret->markAsExitNode(foozle);
1785       }
1786   }
1787
1788   for (std::list<Node::Ptr>::iterator tmp =
1789            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1790       ret->deleteNode(*tmp);
1791   }
1792   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1793 }
1794
1795 // promotes nodes in the slice graph to termination nodes.
1796 // essentially, the slicer maintains a set of nodes that 
1797 // may be entry/exit nodes for the backwards/fowards case.
1798 // this function removes the nodes from the set, and 
1799 // marks them in the graph as true entry/exit nodes.
1800 // in the forward case, the entry node is a single node,
1801 // the assignment from which the slice began. in the backward
1802 // case, this node is the single exit node. exit nodes in the
1803 // forward case are definitions that are still live at function
1804 // exit. entry nodes in the backward case are uses for which the
1805 // definition lies outside the function (before entry) or move
1806 // instructions where one operand is a literal.
1807 void Slicer::promotePlausibleNodes(GraphPtr g, Direction d) {
1808     // note: it would be better to reuse some other
1809     // functions here, but none of them quite use 
1810     // the interface we need here.
1811     if (d == forward) {
1812         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1813              first != last; ++first) {
1814             g->markAsExitNode(*first);
1815         }
1816     } else {
1817         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1818              first != last; ++first) {
1819             g->markAsEntryNode(*first);
1820         }
1821     }
1822     plausibleNodes.clear();
1823 }
1824
1825 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1826                                    Direction dir) {
1827   return ((dir == forward) ? e->trg() : e->src());
1828 }
1829
1830 bool Slicer::isWidenNode(Node::Ptr n) {
1831   SliceNode::Ptr foozle =
1832     boost::dynamic_pointer_cast<SliceNode>(n);
1833   if (!foozle) return false;
1834   if (!foozle->assign()) return true;
1835   return false;
1836 }
1837
1838 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1839   if (dir == forward) {
1840     // Entry node
1841     ret->insertEntryNode(aP);
1842   }
1843   else {
1844     ret->insertExitNode(aP);
1845   }
1846 }
1847
1848 // creates the initial slice frame and initializes instance variables.
1849 void Slicer::constructInitialFrame(
1850     Direction dir,
1851     SliceFrame & initFrame)
1852 {
1853     Instruction::Ptr init_instruction;
1854     initFrame.con.push_front(ContextElement(f_));
1855     initFrame.loc = Location(f_,b_);
1856
1857     // increment iterators to initial instruction. 
1858     if(dir == forward) {
1859         initFrame.loc.fwd = true;
1860         getInsns(initFrame.loc);
1861         fastForward(initFrame.loc, a_->addr());
1862         init_instruction = initFrame.loc.current->first;
1863     } else {
1864         initFrame.loc.fwd = false;
1865         getInsnsBackward(initFrame.loc);
1866         fastBackward(initFrame.loc, a_->addr());
1867         init_instruction = initFrame.loc.rcurrent->first;
1868     }
1869
1870     // reconstruct initial assignment. the initial assignment was created
1871     // by a different converter, and thus if the instruction is visited
1872     // more than once by the slicer, the assignment will be recreated
1873     // instead of coming out of cache. this results in duplicated graph
1874     // nodes. 
1875     std::vector<Assignment::Ptr> assigns;
1876     convertInstruction(init_instruction, a_->addr(), f_, b_, assigns);
1877     for (auto first = assigns.begin(), last = assigns.end(); first != last; ++first) {
1878         if ((*first)->out() == a_->out()) { a_ = *first; break; }
1879     }
1880
1881     if(dir == forward) {
1882         Element oe(b_,f_,a_->out(),a_);
1883         initFrame.active[a_->out()].push_back(oe);
1884     } else {
1885         vector<AbsRegion> & inputs = a_->inputs();
1886         vector<AbsRegion>::iterator iit = inputs.begin();
1887         for ( ; iit != inputs.end(); ++iit) {
1888             Element ie(b_,f_,*iit,a_);
1889             initFrame.active[*iit].push_back(ie);
1890         }
1891     }
1892 }
1893
1894 void
1895 Slicer::DefCache::merge(Slicer::DefCache const& o)
1896 {
1897     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1898     for( ; oit != o.defmap.end(); ++oit) {
1899         AbsRegion const& r = oit->first;
1900         set<Def> const& s = oit->second;
1901         defmap[r].insert(s.begin(),s.end());
1902     }
1903 }
1904
1905 void
1906 Slicer::DefCache::replace(Slicer::DefCache const& o)
1907 {   
1908     // XXX if o.defmap[region] is empty set, remove that entry
1909     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1910     for( ; oit != o.defmap.end(); ++oit) {
1911         if(!(*oit).second.empty())
1912             defmap[(*oit).first] = (*oit).second;
1913         else
1914             defmap.erase((*oit).first);
1915     }
1916 }
1917
1918 void
1919 Slicer::DefCache::print() const {
1920     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1921     for( ; it !=defmap.end(); ++it) {
1922         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1923         set<Def> const& defs = (*it).second;
1924         set<Def>::const_iterator dit = defs.begin();
1925         for( ; dit != defs.end(); ++dit) {
1926             slicing_printf("\t\t\t<%s,%s>\n",
1927                 (*dit).ele.ptr->format().c_str(),
1928                 (*dit).data.format().c_str());
1929         }
1930     }
1931 }
1932
1933 // merges all single caches that have occured single addr in the
1934 // recursion into the appropriate unified caches.
1935 void Slicer::mergeRecursiveCaches(std::map<Address, DefCache>& single, 
1936                                   std::map<Address, DefCache>& unified, Address addr) {
1937
1938
1939     for (auto first = addrStack.rbegin(), last = addrStack.rend();
1940             first != last; ++first) {
1941         unified[*first].replace(single[*first]);
1942         auto next = first + 1;
1943         if (next != last) {
1944             unified[*next].merge(unified[*first]);
1945         }
1946     }
1947 }
1948