Fix conflicts between caching and stopping slicing
[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 (cur.loc.block->obj()->cs()->getAddressWidth() == 8)
1164                     cur.active[AbsRegion(Absloc(x86_64::rip))] = newE;
1165                 else if  (cur.loc.block->obj()->cs()->getAddressWidth() == 4)
1166                     cur.active[AbsRegion(Absloc(x86::eip))] = newE;
1167 //          }
1168
1169             cur.firstCond = false;
1170             slicing_printf("\tadding tracking ip for control flow information ");
1171         }
1172     }
1173     return true;
1174 }
1175
1176 /* ----------------- backwards slicing implementations ------------------ */
1177
1178 bool
1179 Slicer::handleCallBackward(
1180     Predicates & p,
1181     SliceFrame const& cand,
1182     vector<SliceFrame> & newCands,
1183     ParseAPI::Edge * e,
1184     bool & /* err */)
1185 {
1186     // We don't know which function the caller block belongs to,
1187     // so check each possibility against the predicate.
1188     //
1189     // XXX   this suffers the same problem as followCall in the forward
1190     //       case; the predicates test against only a single abstract
1191     //       region. What we do here is to build up mappings from
1192     //       function paths (that will be followed) to sets of abstract
1193     //       regions, then create SliceFrames with these sets.
1194
1195     map<ParseAPI::Function *, SliceFrame::ActiveMap > fmap;
1196
1197     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1198     for( ; ait != cand.active.end(); ++ait) {
1199         vector<ParseAPI::Function *> follow = 
1200             followCallBackward(p,cand,(*ait).first,e->src());
1201         for(unsigned j=0;j<follow.size();++j) {
1202             fmap[follow[j]].insert(*ait);
1203         }
1204     }
1205
1206     map<ParseAPI::Function *, SliceFrame::ActiveMap >::iterator mit = 
1207         fmap.begin();
1208     for( ; mit != fmap.end(); ++mit) {
1209         ParseAPI::Function * f = (*mit).first;
1210         SliceFrame::ActiveMap & act = (*mit).second;
1211     
1212         SliceFrame nf(cand.loc,cand.con, cand.firstCond);
1213         nf.active = act;
1214
1215         nf.con.push_back(ContextElement(f));
1216         nf.loc.block = e->src();
1217         nf.loc.func = f;
1218
1219         // pop context & adjust AbsRegions
1220         if(!handleCallDetailsBackward(nf)) {
1221             // FIXME I have preserved this behavior (returning false if
1222             //       the current frame can't be adjusted). It seems to
1223             //       me that we ought to set err = true and continue
1224             //       processing the rest of the call edges.
1225             //
1226             //       This issue needs review by somebody knowledgeable
1227             //       about the slicer.
1228             return false;
1229         }
1230
1231         getInsnsBackward(nf.loc);
1232         newCands.push_back(nf);
1233     } 
1234     return true;
1235 }
1236
1237 /*
1238  * FIXME egregious copying
1239  */
1240 vector<ParseAPI::Function *>
1241 Slicer::followCallBackward(
1242     Predicates & p,
1243     SliceFrame const& cand,
1244     AbsRegion const& reg,
1245     ParseAPI::Block * caller_block)
1246 {
1247     stack< pair<ParseAPI::Function *, int> > callStack;  
1248     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1249         calls != cand.con.rend(); ++calls)
1250     {
1251         if(calls->func) {
1252             callStack.push(
1253                std::make_pair(calls->func, calls->stackDepth));
1254         }
1255     }
1256     return p.followCallBackward(caller_block, callStack, reg);
1257 }
1258
1259 bool
1260 Slicer::handleCallDetailsBackward(
1261     SliceFrame & cur)
1262 {
1263     ParseAPI::Block * callBlock = cur.loc.block;
1264     ParseAPI::Function * caller = cur.loc.func;
1265
1266     Address callBlockLastInsn = callBlock->lastInsnAddr();
1267
1268     long stack_depth;
1269     if(!getStackDepth(caller, callBlock, callBlockLastInsn,stack_depth)) {
1270         return false;
1271     }
1272
1273     popContext(cur.con);
1274     assert(!cur.con.empty());
1275
1276
1277     slicing_printf("\t%s, %d\n",
1278         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1279         cur.con.front().stackDepth);
1280
1281     // Transform the active abstract regions
1282     shiftAllAbsRegions(cur,-1*stack_depth,caller);
1283
1284     return true;
1285 }
1286     
1287 bool
1288 Slicer::handleReturnBackward(
1289     Predicates & p,
1290     SliceFrame const& cand,
1291     SliceFrame & newCand,
1292     ParseAPI::Edge * e,
1293     bool & err)
1294 {
1295     ParseAPI::Block * callee = e->src();
1296
1297     // cons up a call stack for the call associated
1298     // with this return and ask the predicates whether
1299     // they would have come down this call.
1300     //
1301     // FIXME the issue of predicates evaluating only a
1302     //       single abstract region applies here as well;
1303     //       see comments in handleCall and handleCallBackward
1304
1305     if(followReturn(p,cand,callee)) {
1306         // XXX it is not clear to me why a null callee is an error here
1307         //     but not if followReturn returns false FIXME
1308         if(!callee) {
1309             err = true;
1310             return false;
1311         }
1312
1313         newCand = cand;
1314         newCand.loc.block = callee;
1315         newCand.loc.func = getEntryFunc(callee);
1316         getInsnsBackward(newCand.loc);
1317
1318         if(!handleReturnDetailsBackward(newCand,cand.loc.block)) {
1319             err = true;
1320             return false;
1321         }
1322         return true;
1323     } 
1324     return false;
1325 }
1326
1327 bool
1328 Slicer::handleReturnDetailsBackward(
1329     SliceFrame & cur,
1330     ParseAPI::Block * caller_block)
1331 {
1332     ParseAPI::Function * caller = cur.con.front().func;
1333     ParseAPI::Function * callee = cur.loc.func;
1334
1335     long stack_depth;
1336     if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
1337         return false;
1338     }
1339     
1340     pushContext(cur.con, callee, caller_block, stack_depth);
1341
1342     // Transform the active abstract regions
1343     shiftAllAbsRegions(cur,stack_depth,caller);
1344
1345     return true; 
1346 }
1347
1348 bool
1349 Slicer::followReturn(
1350     Predicates & p,
1351     SliceFrame const& cand,
1352     ParseAPI::Block * source)
1353 {
1354     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1355     
1356     stack< pair<ParseAPI::Function *, int> > callStack;
1357     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1358         calls != cand.con.rend(); ++calls)
1359     {
1360         if(calls->func) {
1361             callStack.push(
1362                std::make_pair(calls->func, calls->stackDepth));
1363         }
1364     }
1365
1366     bool ret = false;
1367     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1368     for( ; ait != cand.active.end(); ++ait) {
1369         ret = ret || p.followCall(callee,callStack,(*ait).first);
1370     }
1371     return ret;
1372 }
1373     
1374
1375
1376 /* ------------------------------------------- */
1377
1378 Address SliceNode::addr() const { 
1379   if (a_)
1380     return a_->addr();
1381   return 0;
1382 }
1383
1384 bool containsCall(ParseAPI::Block *block) {
1385   // We contain a call if the out-edges include
1386   // either a CALL or a CALL_FT edge
1387   const Block::edgelist &targets = block->targets();
1388   Block::edgelist::const_iterator eit = targets.begin();
1389   for (; eit != targets.end(); ++eit) {
1390     ParseAPI::Edge *edge = *eit;
1391     if (edge->type() == CALL) return true;
1392   }
1393   return false;
1394 }
1395
1396 bool containsRet(ParseAPI::Block *block) {
1397   // We contain a call if the out-edges include
1398   // either a CALL or a CALL_FT edge
1399   const Block::edgelist &targets = block->targets();
1400   Block::edgelist::const_iterator eit = targets.begin();
1401   for (; eit != targets.end(); ++eit) {
1402     ParseAPI::Edge *edge = *eit;
1403     if (edge->type() == RET) return true;
1404   }
1405   return false;
1406 }
1407
1408 static void getInsnInstances(ParseAPI::Block *block,
1409                       Slicer::InsnVec &insns) {
1410   Offset off = block->start();
1411   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
1412   if (ptr == NULL) return;
1413   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
1414   while (off < block->end()) {
1415     insns.push_back(std::make_pair(d.decode(), off));
1416     off += insns.back().first->size();
1417   }
1418 }
1419
1420 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
1421   return block->obj()->findFuncByEntry(block->region(), block->start());
1422 }
1423
1424 // Constructor. Takes the initial point we slice from. 
1425
1426 // TODO: make this function-less interprocedural. That would throw the
1427 // stack analysis for a loop, but is generally doable...
1428 Slicer::Slicer(Assignment::Ptr a,
1429                ParseAPI::Block *block,
1430                ParseAPI::Function *func) : 
1431   a_(a),
1432   b_(block),
1433   f_(func),
1434   // Xiaozhu: Temporarily disable stackanalysis, should be able to
1435   // specify it 
1436   converter(false, false) {
1437   df_init_debug();
1438 };
1439
1440 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
1441
1442         // delete cache state
1443   unique_edges_.clear(); 
1444
1445   return sliceInternal(forward, predicates);
1446 }
1447
1448 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
1449   // delete cache state
1450   unique_edges_.clear(); 
1451
1452   return sliceInternal(backward, predicates);
1453 }
1454
1455 bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
1456   StackAnalysis sA(func);
1457
1458   StackAnalysis::Height heightSA = sA.findSP(block, callAddr);
1459
1460   // Ensure that analysis has been performed.
1461
1462   assert(!heightSA.isTop());
1463   
1464   if (heightSA.isBottom()) {
1465     return false;
1466   }
1467   
1468   height = heightSA.height();
1469   
1470   // The height will include the effects of the call
1471   // Should check the region... 
1472
1473   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
1474   //<< std::dec << " " << (int) height << endl;
1475
1476   return true;
1477 }
1478
1479 void Slicer::pushContext(Context &context,
1480                          ParseAPI::Function *callee,
1481                          ParseAPI::Block *callBlock,
1482                          long stackDepth) {
1483   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
1484   assert(context.front().block == NULL);
1485   context.front().block = callBlock;
1486
1487   slicing_cerr << "\t" 
1488                << (context.front().func ? context.front().func->name() : "NULL")
1489                << ", " 
1490                << context.front().stackDepth 
1491                << endl;
1492
1493     context.push_front(ContextElement(callee, stackDepth));
1494 };
1495
1496 void Slicer::popContext(Context &context) {
1497   context.pop_front();
1498
1499   context.front().block = NULL;
1500 }
1501
1502 void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
1503                             AbsRegion &calleeReg,
1504                             long stack_depth,
1505                             ParseAPI::Function *callee) {
1506   if (callerReg.absloc() == Absloc()) {
1507     // Typed, so just keep the same type and call it a day
1508     calleeReg = callerReg;
1509     return;
1510   }
1511   else {
1512     assert(callerReg.type() == Absloc::Unknown);
1513     
1514     const Absloc &callerAloc = callerReg.absloc();
1515     if (callerAloc.type() != Absloc::Stack) {
1516       calleeReg = AbsRegion(callerAloc);
1517     }
1518     else {
1519       if (stack_depth == -1) {
1520         // Oops
1521         calleeReg = AbsRegion(Absloc::Stack);
1522         return;
1523       }
1524       else {
1525         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
1526         //<< " by stack depth " << stack_depth 
1527         //<< " and setting to function " << callee->name() << endl;
1528         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
1529                                      0, // Entry point has region 0 by definition
1530                                      callee));
1531       }
1532     }
1533   }
1534 }
1535
1536 bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
1537   // Did we find a definition of the same abstract region?
1538   // TBD: overlaps ins't quite the right thing here. "contained
1539   // by" would be better, but we need to get the AND/OR
1540   // of abslocs hammered out.
1541   
1542   if (assign->out().type() != Absloc::Unknown) {
1543     // A region assignment can never kill
1544     return false; 
1545   }
1546
1547   if (assign->insn()->getOperation().getID() == e_call && reg.absloc().type() == Absloc::Register) {
1548       MachRegister r = reg.absloc().reg();
1549       ABI* abi = ABI::getABI(b_->obj()->cs()->getAddressWidth());
1550       int index = abi->getIndex(r);
1551       if (index >= 0)
1552           if (abi->getCallWrittenRegisters()[abi->getIndex(r)]) return true;
1553   }
1554   return reg.contains(assign->out());
1555 }
1556
1557 // creates a new node from an element if that node does not yet exist.
1558 // otherwise, it returns the pre-existing node.
1559 SliceNode::Ptr Slicer::createNode(Element const&elem) {
1560   if (created_.find(elem.ptr) != created_.end()) {
1561     return created_[elem.ptr];
1562   }
1563   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
1564   created_[elem.ptr] = newNode;
1565
1566   // mark this node as plausibly being entry/exit.
1567   plausibleNodes.insert(newNode); 
1568   return newNode;
1569 }
1570
1571 std::string SliceNode::format() const {
1572   if (!a_) {
1573     return "<NULL>";
1574   }
1575
1576   stringstream ret;
1577   ret << "(" << a_->format() << "@" <<
1578     f_->name() << ")";
1579   return ret.str();
1580 }
1581
1582 // converts an instruction to a vector of assignments. if this slicer has
1583 // already converted this instruction, this function returns the same
1584 // assignments.
1585 // Note that we CANNOT use a global cache based on the address
1586 // of the instruction to convert because the block that contains
1587 // the instructino may change during parsing.
1588 void Slicer::convertInstruction(Instruction::Ptr insn,
1589                                 Address addr,
1590                                 ParseAPI::Function *func,
1591                                 ParseAPI::Block *block,
1592                                 std::vector<Assignment::Ptr> &ret) {
1593   converter.convert(insn,
1594                     addr,
1595                     func,
1596                     block,
1597                     ret);
1598   return;
1599 }
1600
1601 void Slicer::getInsns(Location &loc) {
1602
1603
1604   InsnCache::iterator iter = insnCache_.find(loc.block);
1605   if (iter == insnCache_.end()) {
1606     getInsnInstances(loc.block, insnCache_[loc.block]);
1607   }
1608   
1609   loc.current = insnCache_[loc.block].begin();
1610   loc.end = insnCache_[loc.block].end();
1611 }
1612
1613 void Slicer::getInsnsBackward(Location &loc) {
1614     assert(loc.block->start() != (Address) -1); 
1615     InsnCache::iterator iter = insnCache_.find(loc.block);
1616     if (iter == insnCache_.end()) {
1617       getInsnInstances(loc.block, insnCache_[loc.block]);
1618     }
1619
1620     loc.rcurrent = insnCache_[loc.block].rbegin();
1621     loc.rend = insnCache_[loc.block].rend();
1622 }
1623
1624 // inserts an edge from source to target (forward) or target to source
1625 // (backward) if the edge does not yet exist. this is done by converting
1626 // source and target to graph nodes (creating them if they do not exist).
1627 void Slicer::insertPair(Graph::Ptr ret,
1628                         Direction dir,
1629                         Element const&source,
1630                         Element const&target,
1631                         AbsRegion const& data) 
1632 {
1633     SliceNode::Ptr s = createNode(source);
1634     SliceNode::Ptr t = createNode(target);
1635
1636     insertPair(ret, dir, s, t, data);
1637 }
1638
1639 // inserts an edge from source to target (forward) or target to source
1640 // (backward) if the edge does not yet exist.
1641 void Slicer::insertPair(Graph::Ptr ret,
1642                         Direction dir,
1643                         SliceNode::Ptr& s,
1644                         SliceNode::Ptr& t,
1645                         AbsRegion const& data) 
1646 {
1647
1648   EdgeTuple et(s,t,data);
1649   if(unique_edges_.find(et) != unique_edges_.end()) {
1650     unique_edges_[et] += 1;
1651     return;
1652   }
1653   unique_edges_[et] = 1;  
1654
1655   if (dir == forward) {
1656      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1657      ret->insertPair(s, t, e);
1658
1659      // this node is clearly not entry/exit.
1660      plausibleNodes.erase(s);
1661   } else {
1662      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1663      ret->insertPair(t, s, e);
1664
1665      // this node is clearly not entry/exit.
1666      plausibleNodes.erase(s); 
1667   }
1668 }
1669
1670 void
1671 Slicer::widenAll(
1672     Graph::Ptr g,
1673     Direction dir,
1674     SliceFrame const& cand)
1675 {
1676     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1677     for( ; ait != cand.active.end(); ++ait) {
1678         vector<Element> const& eles = (*ait).second;
1679         for(unsigned i=0;i<eles.size();++i)
1680             widen(g,dir,eles[i]);
1681     }
1682 }
1683
1684 void Slicer::widen(Graph::Ptr ret,
1685                    Direction dir,
1686                    Element const&e) {
1687   if (dir == forward) {
1688     ret->insertPair(createNode(e),
1689                     widenNode());
1690     ret->insertExitNode(widenNode());
1691   }
1692   else {
1693     ret->insertPair(widenNode(), createNode(e));
1694     ret->insertEntryNode(widenNode());
1695   }
1696 }
1697
1698 SliceNode::Ptr Slicer::widenNode() {
1699   if (widen_) {
1700     return widen_;
1701   }
1702
1703   widen_ = SliceNode::create(Assignment::Ptr(),
1704                               NULL, NULL);
1705   return widen_;
1706 }
1707
1708 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1709   if (dir == forward) {    
1710     ret->insertExitNode(createNode(e));
1711   }
1712   else {
1713     ret->insertEntryNode(createNode(e));
1714   }
1715 }
1716
1717 void Slicer::fastForward(Location &loc, Address
1718                          addr) {
1719   while ((loc.current != loc.end) &&
1720          (loc.addr() < addr)) {
1721     loc.current++;
1722   }
1723   assert(loc.current != loc.end);
1724   assert(loc.addr() == addr);
1725 }
1726
1727 void Slicer::fastBackward(Location &loc, Address addr) {
1728     while ((loc.rcurrent != loc.rend) &&
1729          (loc.addr() > addr)) {
1730     loc.rcurrent++;
1731   }
1732   assert(loc.rcurrent != loc.rend);
1733   assert(loc.addr() == addr);  
1734 }
1735
1736 // removes unnecessary nodes from the slice graph. this is
1737 // currently mostly ia32/amd64 flags that are written but
1738 // never read. 
1739 void Slicer::cleanGraph(Graph::Ptr ret) {
1740   slicing_cerr << "Cleaning up the graph..." << endl;
1741   // Clean the graph up
1742   
1743   // TODO: make this more efficient by backwards traversing.
1744   // For now, I know that we're generating graphs with tons of
1745   // unnecessary flag sets (which are immediately killed) and so
1746   // we don't have long non-exiting chains, we have "fuzz"
1747   
1748   NodeIterator nbegin, nend;
1749   ret->allNodes(nbegin, nend);
1750   
1751   std::list<Node::Ptr> toDelete;
1752   unsigned numNodes = 0;
1753   for (; nbegin != nend; ++nbegin) {
1754           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1755       numNodes++;
1756       SliceNode::Ptr foozle =
1757           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1758       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1759       if ((*nbegin)->hasOutEdges()) {
1760           slicing_cerr << "\t has out edges, leaving in" << endl;
1761           continue;
1762       }
1763
1764       // don't remove entry/exit nodes.
1765       if (ret->isEntryNode(*nbegin) || ret->isExitNode(*nbegin)) {
1766           continue;
1767       }
1768
1769       // mark non-flags nodes as exit nodes. these nodes are likely
1770       // relevant to the slice and should not be deleted. only delete 
1771       // flag nodes. this should stop the over-deleting by this
1772       // function, but this is a fairly ugly way of doing it. 
1773       const Absloc& abs = foozle->a_->out().absloc();
1774       if (abs.type() == Absloc::Register && 
1775                         (abs.reg().getArchitecture() == Arch_x86 
1776                          || abs.reg().getArchitecture() == Arch_x86_64) && 
1777                         (abs.reg().getBaseRegister() & x86::FLAG) == x86::FLAG) {
1778           slicing_cerr << "\t deleting" << endl;
1779           toDelete.push_back(*nbegin);
1780       } else {
1781           ret->markAsExitNode(foozle);
1782       }
1783   }
1784
1785   for (std::list<Node::Ptr>::iterator tmp =
1786            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1787       ret->deleteNode(*tmp);
1788   }
1789   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1790 }
1791
1792 // promotes nodes in the slice graph to termination nodes.
1793 // essentially, the slicer maintains a set of nodes that 
1794 // may be entry/exit nodes for the backwards/fowards case.
1795 // this function removes the nodes from the set, and 
1796 // marks them in the graph as true entry/exit nodes.
1797 // in the forward case, the entry node is a single node,
1798 // the assignment from which the slice began. in the backward
1799 // case, this node is the single exit node. exit nodes in the
1800 // forward case are definitions that are still live at function
1801 // exit. entry nodes in the backward case are uses for which the
1802 // definition lies outside the function (before entry) or move
1803 // instructions where one operand is a literal.
1804 void Slicer::promotePlausibleNodes(GraphPtr g, Direction d) {
1805     // note: it would be better to reuse some other
1806     // functions here, but none of them quite use 
1807     // the interface we need here.
1808     if (d == forward) {
1809         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1810              first != last; ++first) {
1811             g->markAsExitNode(*first);
1812         }
1813     } else {
1814         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1815              first != last; ++first) {
1816             g->markAsEntryNode(*first);
1817         }
1818     }
1819     plausibleNodes.clear();
1820 }
1821
1822 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1823                                    Direction dir) {
1824   return ((dir == forward) ? e->trg() : e->src());
1825 }
1826
1827 bool Slicer::isWidenNode(Node::Ptr n) {
1828   SliceNode::Ptr foozle =
1829     boost::dynamic_pointer_cast<SliceNode>(n);
1830   if (!foozle) return false;
1831   if (!foozle->assign()) return true;
1832   return false;
1833 }
1834
1835 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1836   if (dir == forward) {
1837     // Entry node
1838     ret->insertEntryNode(aP);
1839   }
1840   else {
1841     ret->insertExitNode(aP);
1842   }
1843 }
1844
1845 // creates the initial slice frame and initializes instance variables.
1846 void Slicer::constructInitialFrame(
1847     Direction dir,
1848     SliceFrame & initFrame)
1849 {
1850     Instruction::Ptr init_instruction;
1851     initFrame.con.push_front(ContextElement(f_));
1852     initFrame.loc = Location(f_,b_);
1853
1854     // increment iterators to initial instruction. 
1855     if(dir == forward) {
1856         initFrame.loc.fwd = true;
1857         getInsns(initFrame.loc);
1858         fastForward(initFrame.loc, a_->addr());
1859         init_instruction = initFrame.loc.current->first;
1860     } else {
1861         initFrame.loc.fwd = false;
1862         getInsnsBackward(initFrame.loc);
1863         fastBackward(initFrame.loc, a_->addr());
1864         init_instruction = initFrame.loc.rcurrent->first;
1865     }
1866
1867     // reconstruct initial assignment. the initial assignment was created
1868     // by a different converter, and thus if the instruction is visited
1869     // more than once by the slicer, the assignment will be recreated
1870     // instead of coming out of cache. this results in duplicated graph
1871     // nodes. 
1872     std::vector<Assignment::Ptr> assigns;
1873     convertInstruction(init_instruction, a_->addr(), f_, b_, assigns);
1874     for (auto first = assigns.begin(), last = assigns.end(); first != last; ++first) {
1875         if ((*first)->out() == a_->out()) { a_ = *first; break; }
1876     }
1877
1878     if(dir == forward) {
1879         Element oe(b_,f_,a_->out(),a_);
1880         initFrame.active[a_->out()].push_back(oe);
1881     } else {
1882         vector<AbsRegion> & inputs = a_->inputs();
1883         vector<AbsRegion>::iterator iit = inputs.begin();
1884         for ( ; iit != inputs.end(); ++iit) {
1885             Element ie(b_,f_,*iit,a_);
1886             initFrame.active[*iit].push_back(ie);
1887         }
1888     }
1889 }
1890
1891 void
1892 Slicer::DefCache::merge(Slicer::DefCache const& o)
1893 {
1894     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1895     for( ; oit != o.defmap.end(); ++oit) {
1896         AbsRegion const& r = oit->first;
1897         set<Def> const& s = oit->second;
1898         defmap[r].insert(s.begin(),s.end());
1899     }
1900 }
1901
1902 void
1903 Slicer::DefCache::replace(Slicer::DefCache const& o)
1904 {   
1905     // XXX if o.defmap[region] is empty set, remove that entry
1906     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1907     for( ; oit != o.defmap.end(); ++oit) {
1908         if(!(*oit).second.empty())
1909             defmap[(*oit).first] = (*oit).second;
1910         else
1911             defmap.erase((*oit).first);
1912     }
1913 }
1914
1915 void
1916 Slicer::DefCache::print() const {
1917     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1918     for( ; it !=defmap.end(); ++it) {
1919         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1920         set<Def> const& defs = (*it).second;
1921         set<Def>::const_iterator dit = defs.begin();
1922         for( ; dit != defs.end(); ++dit) {
1923             slicing_printf("\t\t\t<%s,%s>\n",
1924                 (*dit).ele.ptr->format().c_str(),
1925                 (*dit).data.format().c_str());
1926         }
1927     }
1928 }
1929
1930 // merges all single caches that have occured single addr in the
1931 // recursion into the appropriate unified caches.
1932 void Slicer::mergeRecursiveCaches(std::map<Address, DefCache>& single, 
1933                                   std::map<Address, DefCache>& unified, Address addr) {
1934
1935
1936     for (auto first = addrStack.rbegin(), last = addrStack.rend();
1937             first != last; ++first) {
1938         unified[*first].replace(single[*first]);
1939         auto next = first + 1;
1940         if (next != last) {
1941             unified[*next].merge(unified[*first]);
1942         }
1943     }
1944 }
1945