1. Add a callback interface to slicing code. It triggers when a new node is added...
[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_)) {
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 (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])) 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   switch(e->type()) 
720   {
721   case CALL:
722     slicing_printf("\t\t Handling call... ");
723     if(handleCallBackward(p,cand,newCands,e,err)) {
724       slicing_printf("succeess, err: %d\n",err);
725     } else {
726       slicing_printf("failed, err: %d\n",err);
727     }
728     break;
729   case RET:
730     slicing_printf("\t\t Handling return... ");
731     nf = cand;
732     if(handleReturnBackward(p,cand,nf,e,err)) {
733       slicing_printf("succeess, err: %d\n",err);
734     } else {
735       slicing_printf("failed, err: %d\n",err);
736     }
737     break;
738   default:
739     nf = cand;
740     slicing_printf("\t\t Handling default edge type %d... ",
741                    e->type());
742     if(handleDefault(backward,p,e,nf,err)) {
743       slicing_printf("success, err: %d\n",err);
744       newCands.push_back(nf);
745     } else {
746       slicing_printf("failed, err: %d\n",err);
747     }
748   }
749 }
750
751
752   
753
754 /*
755  * Same as successors, only backwards
756  */
757 bool
758 Slicer::getPredecessors(
759     Predicates &p,
760     SliceFrame const& cand,
761     vector<SliceFrame> & newCands)
762 {
763     static clock_t getPredecessorsIntraTime = 0, 
764                    getPredecessorsInterTime = 0,
765                    t;
766 //    t = clock();
767     InsnVec::reverse_iterator prev = cand.loc.rcurrent;
768     ++prev;
769
770     // Case 1: intra-block
771     if(prev != cand.loc.rend) {
772         SliceFrame nf(cand.loc,cand.con, cand.firstCond);
773         nf.loc.rcurrent = prev;
774
775         // Slightly more complicated than the forward case; check
776         // a predicate for each active abstract region to see whether
777         // we should continue
778         bool cont = false;
779         SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
780         for( ; ait != cand.active.end(); ++ait) {
781             bool add = p.addPredecessor((*ait).first);
782             if(add)
783                 nf.active.insert(*ait);
784             cont = cont || add;
785         }
786
787         if(cont) {
788             slicing_printf("\t\t\t\t Adding intra-block predecessor %lx\n",
789                 nf.loc.addr());
790             slicing_printf("\t\t\t\t Current regions are:\n");
791             if(slicing_debug_on()) {
792                 SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
793                 for( ; ait != cand.active.end(); ++ait) {
794                     slicing_printf("\t\t\t\t%s\n",
795                         (*ait).first.format().c_str());
796
797                         vector<Element> const& eles = (*ait).second;
798                         for(unsigned i=0;i<eles.size();++i) {
799                                 slicing_printf("\t\t\t\t\t [%s] : %s\n",
800                                         eles[i].reg.format().c_str(),eles[i].ptr->format().c_str());
801                         }
802                 }
803             }
804     
805             newCands.push_back(nf);
806         }
807 //      getPredecessorsIntraTime += clock() - t;
808 //      fprintf(stderr, "getPredecessors (intra): %.3lf\n", (float)getPredecessorsIntraTime / CLOCKS_PER_SEC);
809         return true;
810     }
811
812     // Case 2: inter-block
813     bool err = false;
814     SliceFrame nf;
815     
816     SingleContextOrInterproc epred(cand.loc.func, true, true);
817
818     const Block::edgelist & sources = cand.loc.block->sources();
819     std::for_each(boost::make_filter_iterator(epred, sources.begin(), sources.end()),
820                   boost::make_filter_iterator(epred, sources.end(), sources.end()),
821                   boost::bind<void>(&Slicer::handlePredecessorEdge,
822                                     this,
823                                     _1,
824                                     boost::ref(p),
825                                     boost::ref(cand),
826                                     boost::ref(newCands),
827                                     boost::ref(err),
828                                     boost::ref(nf)
829                                     ));
830 //    getPredecessorsInterTime += clock() - t;
831 //    fprintf(stderr, "getPredecessors (inter): %.3lf\n", (float)getPredecessorsInterTime / CLOCKS_PER_SEC);
832
833     return !err; 
834 }
835
836 /*
837  * Process a call instruction, determining whether to follow the
838  * call edge (with the help of the predicates) or the fallthrough
839  * edge (coloquially referred to as `funlink' thanks to our 
840  * departed Arizona alum --- much respect M.L.)
841  */
842 bool
843 Slicer::handleCall(
844     Predicates & p,
845     SliceFrame & cur,
846     bool & err)
847 {
848     ParseAPI::Block * callee = NULL;
849     ParseAPI::Edge * funlink = NULL;
850     bool widen = false;
851
852     const Block::edgelist & targets = cur.loc.block->targets();
853     Block::edgelist::const_iterator eit = targets.begin();
854     for( ; eit != targets.end(); ++eit) {
855         ParseAPI::Edge * e = *eit;
856         if (e->sinkEdge()) widen = true;
857         else if(e->type() == CALL) {
858             if (callee && callee != e->trg()) {
859                 // Oops
860                 widen = true;
861             }
862             callee = e->trg();
863         } else if(e->type() == CALL_FT) {
864            funlink = e;
865         }
866     }
867     
868     if(followCall(p, callee, cur)) {
869        if (widen) {
870           // Indirect call that they wanted us to follow, so widen.
871           err = true;
872           return true;
873        }
874
875        ParseAPI::Block * caller_block = cur.loc.block;
876        
877        cur.loc.block = callee;
878        cur.loc.func = getEntryFunc(callee);
879        getInsns(cur.loc);
880        
881        // Update the context of the slicing frame
882        // and modify the abstract regions in its
883        // active vector
884        if(!handleCallDetails(cur,caller_block)) {
885           err = true;
886           return false;
887        }
888     }
889     else {
890         // Use the funlink
891         if(!funlink) {
892             // FIXME I am preserving a comment and semantics that
893             // I do not understand here, again as of 06697df. Quote:
894
895             // ???
896             return false;
897         }
898         if(!handleDefault(forward,p,funlink,cur,err)) {
899             err = true;
900             return false;
901         }
902     }
903     return true;
904 }
905
906 /*
907  * Builds up a call stack and callee function, and ask
908  * the predicate whether we should follow the call (or,
909  * implicitly, follow its fallthrough edge instead).
910  */
911 bool
912 Slicer::followCall(
913     Predicates & p,
914     ParseAPI::Block * target,
915     SliceFrame & cur)
916 {
917     // FIXME quote:
918    // A NULL callee indicates an indirect call.
919    // TODO on that one...
920    
921     ParseAPI::Function * callee = (target ? getEntryFunc(target) : NULL);
922     
923     // cons up a call stack
924     stack< pair<ParseAPI::Function *, int> > callStack;
925     for(Context::reverse_iterator calls = cur.con.rbegin();
926         calls != cur.con.rend(); ++calls)
927     {
928         if(NULL != calls->func) {
929             callStack.push(make_pair(calls->func,calls->stackDepth));
930         }
931     } 
932     // Quote:
933         // FIXME: assuming that this is not a PLT function, since I have no
934         // idea at present.  -- BW, April 2010
935
936     // Give the predicate an opportunity to accept this call for each
937     // of the abstract regions in the active set
938     //
939     // XXX There is an interesting concern here. What if the predicate
940     // would indicate `follow' for one active AbsRegion and `do not
941     // follow' for another? What you'd want to do in that case is
942     // fork into multiple SliceFrames for absregions that should go
943     // one way or the other. This is something that could be done by
944     // moving the handleCallDetails() call into this method and
945     // modifying the nextCands vector here, as opposed to in
946     // handleCall(). 
947     // 
948     // This issue needs review by a person involved in slicer design.
949     // FIXME
950
951     bool ret = false;
952
953     SliceFrame::ActiveMap::iterator ait = cur.active.begin();
954     for( ; ait != cur.active.end(); ++ait) {
955         ret = ret || p.followCall(callee, callStack, (*ait).first);
956     }
957     
958     return ret;
959 }
960
961 void 
962 Slicer::shiftAllAbsRegions(
963     SliceFrame & cur,
964     long stack_depth,
965     ParseAPI::Function *callee)
966 {
967     SliceFrame::ActiveMap newMap;
968
969     // fix all of the abstract regions
970     SliceFrame::ActiveMap::iterator ait = cur.active.begin();
971     for( ; ait != cur.active.end(); ++ait) {
972         AbsRegion const& reg = (*ait).first;
973
974         // shortcut -- do nothing if no adjustment is necessary
975         if(reg.absloc() == Absloc()) {
976             // N.B. doing this the hard way (rather than map.insert()
977             //      in case a previous or later iteration transforms
978             //      a different AbsRegion to the same as (*ait).first
979             vector<Element> & e = newMap[(*ait).first];
980             e.insert(e.end(),(*ait).second.begin(),(*ait).second.end());
981             continue;
982         }
983
984         // Adjust the mapping region, but do not adjust the regions of the
985         // elements --- these are maintained to their old values for
986         // annotating the slicing graph edges to facilitate substitution
987         // in symbolic expansion
988         AbsRegion newReg;
989         shiftAbsRegion(reg,newReg,stack_depth,callee);
990
991         // just copy the elements
992         vector<Element> & e = newMap[newReg];
993         e.insert(e.end(),(*ait).second.begin(),(*ait).second.end());
994     }
995     // and replace
996     cur.active = newMap;    
997 }
998
999 /*
1000  * Adjust the slice frame's context and translates the abstract
1001  * regions in the active list from caller to callee
1002  */
1003 bool
1004 Slicer::handleCallDetails(
1005     SliceFrame & cur,
1006     ParseAPI::Block * caller_block)
1007
1008     ParseAPI::Function * caller = cur.con.front().func;
1009     ParseAPI::Function * callee = cur.loc.func;
1010
1011     long stack_depth = 0;
1012     if(!getStackDepth(caller, caller_block, caller_block->end(), stack_depth))
1013         return false;
1014
1015     // Increment the context
1016     pushContext(cur.con, callee, caller_block, stack_depth);
1017
1018     // Transform the active abstract regions
1019     shiftAllAbsRegions(cur,stack_depth,callee);
1020
1021     return true;
1022 }
1023
1024 /*
1025  * Properly adjusts the location & context of the slice frame and the
1026  * AbsRegions of its active elements
1027  */
1028 bool 
1029 Slicer::handleReturn(
1030     Predicates & /* p */,
1031     SliceFrame & cur,
1032     bool & err)
1033 {
1034     // Sanity check -- when we pop (in handleReturnDetails),
1035     // it should not result in context being empty
1036     //
1037     // FIXME I duplicated this from the old version; I don't
1038     //       understand why this doesn't set err = false.
1039     if(cur.con.size() <= 1)
1040         return false;
1041
1042     // Find successor
1043     ParseAPI::Block * retBlock = NULL;
1044     
1045     const Block::edgelist & targets = cur.loc.block->targets();
1046     Block::edgelist::const_iterator eit = targets.begin();
1047     for(; eit != targets.end(); ++eit) {
1048         if((*eit)->type() == CALL_FT) {
1049             retBlock = (*eit)->trg();
1050             if ((*eit)->sinkEdge()) {
1051                 cerr << "Weird!" << endl;
1052             }
1053             break;
1054         }
1055     }
1056     if(!retBlock) {
1057         err = true;
1058         return false;
1059     }
1060
1061     // Pops a context and adjusts the abstract regions in `active'
1062     handleReturnDetails(cur);
1063
1064     // Fix location given new context
1065     cur.loc.func = cur.con.front().func;
1066     cur.loc.block = retBlock;
1067     getInsns(cur.loc);
1068
1069     return true;
1070 }
1071
1072 /*
1073  * Do the actual context popping and active AbsRegion translation
1074  */
1075 void
1076 Slicer::handleReturnDetails(
1077     SliceFrame & cur)
1078 {
1079     long stack_depth = cur.con.front().stackDepth;
1080     popContext(cur.con);
1081
1082     assert(!cur.con.empty());
1083
1084     slicing_printf("\t%s, \n",
1085         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1086         cur.con.front().stackDepth);
1087
1088     // Transform the active abstract regions
1089     shiftAllAbsRegions(cur,-1*stack_depth,cur.con.front().func);
1090 }
1091
1092 static bool EndsWithConditionalJump(ParseAPI::Block *b) {
1093     bool cond = false;
1094     for (auto eit = b->targets().begin(); eit != b->targets().end(); ++eit)
1095         if ((*eit)->type() == COND_TAKEN) cond = true;
1096     return cond;
1097 }
1098
1099 static void DFS(ParseAPI::Block *cur, set<ParseAPI::Block*> &visit, ParseAPI::Edge *ban, set<ParseAPI::Block*> &targets) {
1100     if (visit.find(cur) != visit.end()) return;    
1101     visit.insert(cur);
1102     targets.erase(cur);
1103     if (targets.empty()) return;
1104     for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit)
1105         if ((*eit) != ban && (*eit)->type() != CALL && (*eit)->type() != RET)
1106             DFS((*eit)->trg(), visit, ban, targets);
1107 }
1108 bool Slicer::ReachableFromBothBranches(ParseAPI::Edge *e, vector<Element> &newE) {
1109     static clock_t t1 = 0, t2;
1110 //    t2 = clock();
1111
1112     ParseAPI::Block *start;
1113     start = e->src();
1114     set<ParseAPI::Block*> visited , targets;
1115     for (auto eit = newE.begin(); eit != newE.end(); ++eit)
1116         targets.insert(eit->block);
1117     DFS(start, visited, e, targets);
1118 //    t1 += clock() - t2;
1119 //    fprintf(stderr, "check control flow dependency %.3lf\n", (float)t1 / CLOCKS_PER_SEC);
1120 //    fprintf(stderr, "%d %d\n", visited.size(), targets.size());
1121     return targets.empty();
1122 }
1123
1124
1125 bool
1126 Slicer::handleDefault(
1127     Direction dir,
1128     Predicates & /*p*/,
1129     ParseAPI::Edge * e,
1130     SliceFrame & cur,
1131     bool & /* err */)
1132 {
1133     if(dir == forward) {
1134         cur.loc.block = e->trg();
1135         getInsns(cur.loc);
1136     } else {
1137         cur.loc.block = e->src();
1138         getInsnsBackward(cur.loc);
1139         if ((true || cur.firstCond) && EndsWithConditionalJump(e->src())) {
1140             vector<Element> newE;        
1141             
1142             for (auto ait = cur.active.begin(); ait != cur.active.end(); ++ait) {               
1143                 newE.insert(newE.end(), ait->second.begin(), ait->second.end());
1144             }       
1145 /*
1146             for (auto ait = cur.active.begin(); ait != cur.active.end(); ++ait) {
1147                 vector<Element> & oldE = ait->second; 
1148                 for (auto oit = oldE.begin(); oit != oldE.end(); ++oit)
1149                     if (!f_->postDominates(oit->block, cur.loc.block)) newE.push_back(*oit);
1150             }
1151 */          
1152             if (!ReachableFromBothBranches(e, newE)) {
1153 //            if (!newE.empty()) {    
1154                 if (cur.loc.block->obj()->cs()->getAddressWidth() == 8)
1155                     cur.active[AbsRegion(Absloc(x86_64::rip))] = newE;
1156                 else if  (cur.loc.block->obj()->cs()->getAddressWidth() == 4)
1157                     cur.active[AbsRegion(Absloc(x86::eip))] = newE;
1158             }
1159
1160             cur.firstCond = false;
1161             slicing_printf("\tadding tracking ip for control flow information ");
1162         }
1163     }
1164     return true;
1165 }
1166
1167 /* ----------------- backwards slicing implementations ------------------ */
1168
1169 bool
1170 Slicer::handleCallBackward(
1171     Predicates & p,
1172     SliceFrame const& cand,
1173     vector<SliceFrame> & newCands,
1174     ParseAPI::Edge * e,
1175     bool & /* err */)
1176 {
1177     // We don't know which function the caller block belongs to,
1178     // so check each possibility against the predicate.
1179     //
1180     // XXX   this suffers the same problem as followCall in the forward
1181     //       case; the predicates test against only a single abstract
1182     //       region. What we do here is to build up mappings from
1183     //       function paths (that will be followed) to sets of abstract
1184     //       regions, then create SliceFrames with these sets.
1185
1186     map<ParseAPI::Function *, SliceFrame::ActiveMap > fmap;
1187
1188     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1189     for( ; ait != cand.active.end(); ++ait) {
1190         vector<ParseAPI::Function *> follow = 
1191             followCallBackward(p,cand,(*ait).first,e->src());
1192         for(unsigned j=0;j<follow.size();++j) {
1193             fmap[follow[j]].insert(*ait);
1194         }
1195     }
1196
1197     map<ParseAPI::Function *, SliceFrame::ActiveMap >::iterator mit = 
1198         fmap.begin();
1199     for( ; mit != fmap.end(); ++mit) {
1200         ParseAPI::Function * f = (*mit).first;
1201         SliceFrame::ActiveMap & act = (*mit).second;
1202     
1203         SliceFrame nf(cand.loc,cand.con, cand.firstCond);
1204         nf.active = act;
1205
1206         nf.con.push_back(ContextElement(f));
1207         nf.loc.block = e->src();
1208         nf.loc.func = f;
1209
1210         // pop context & adjust AbsRegions
1211         if(!handleCallDetailsBackward(nf)) {
1212             // FIXME I have preserved this behavior (returning false if
1213             //       the current frame can't be adjusted). It seems to
1214             //       me that we ought to set err = true and continue
1215             //       processing the rest of the call edges.
1216             //
1217             //       This issue needs review by somebody knowledgeable
1218             //       about the slicer.
1219             return false;
1220         }
1221
1222         getInsnsBackward(nf.loc);
1223         newCands.push_back(nf);
1224     } 
1225     return true;
1226 }
1227
1228 /*
1229  * FIXME egregious copying
1230  */
1231 vector<ParseAPI::Function *>
1232 Slicer::followCallBackward(
1233     Predicates & p,
1234     SliceFrame const& cand,
1235     AbsRegion const& reg,
1236     ParseAPI::Block * caller_block)
1237 {
1238     stack< pair<ParseAPI::Function *, int> > callStack;  
1239     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1240         calls != cand.con.rend(); ++calls)
1241     {
1242         if(calls->func) {
1243             callStack.push(
1244                std::make_pair(calls->func, calls->stackDepth));
1245         }
1246     }
1247     return p.followCallBackward(caller_block, callStack, reg);
1248 }
1249
1250 bool
1251 Slicer::handleCallDetailsBackward(
1252     SliceFrame & cur)
1253 {
1254     ParseAPI::Block * callBlock = cur.loc.block;
1255     ParseAPI::Function * caller = cur.loc.func;
1256
1257     Address callBlockLastInsn = callBlock->lastInsnAddr();
1258
1259     long stack_depth;
1260     if(!getStackDepth(caller, callBlock, callBlockLastInsn,stack_depth)) {
1261         return false;
1262     }
1263
1264     popContext(cur.con);
1265     assert(!cur.con.empty());
1266
1267
1268     slicing_printf("\t%s, %d\n",
1269         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1270         cur.con.front().stackDepth);
1271
1272     // Transform the active abstract regions
1273     shiftAllAbsRegions(cur,-1*stack_depth,caller);
1274
1275     return true;
1276 }
1277     
1278 bool
1279 Slicer::handleReturnBackward(
1280     Predicates & p,
1281     SliceFrame const& cand,
1282     SliceFrame & newCand,
1283     ParseAPI::Edge * e,
1284     bool & err)
1285 {
1286     ParseAPI::Block * callee = e->src();
1287
1288     // cons up a call stack for the call associated
1289     // with this return and ask the predicates whether
1290     // they would have come down this call.
1291     //
1292     // FIXME the issue of predicates evaluating only a
1293     //       single abstract region applies here as well;
1294     //       see comments in handleCall and handleCallBackward
1295
1296     if(followReturn(p,cand,callee)) {
1297         // XXX it is not clear to me why a null callee is an error here
1298         //     but not if followReturn returns false FIXME
1299         if(!callee) {
1300             err = true;
1301             return false;
1302         }
1303
1304         newCand = cand;
1305         newCand.loc.block = callee;
1306         newCand.loc.func = getEntryFunc(callee);
1307         getInsnsBackward(newCand.loc);
1308
1309         if(!handleReturnDetailsBackward(newCand,cand.loc.block)) {
1310             err = true;
1311             return false;
1312         }
1313         return true;
1314     } 
1315     return false;
1316 }
1317
1318 bool
1319 Slicer::handleReturnDetailsBackward(
1320     SliceFrame & cur,
1321     ParseAPI::Block * caller_block)
1322 {
1323     ParseAPI::Function * caller = cur.con.front().func;
1324     ParseAPI::Function * callee = cur.loc.func;
1325
1326     long stack_depth;
1327     if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
1328         return false;
1329     }
1330     
1331     pushContext(cur.con, callee, caller_block, stack_depth);
1332
1333     // Transform the active abstract regions
1334     shiftAllAbsRegions(cur,stack_depth,caller);
1335
1336     return true; 
1337 }
1338
1339 bool
1340 Slicer::followReturn(
1341     Predicates & p,
1342     SliceFrame const& cand,
1343     ParseAPI::Block * source)
1344 {
1345     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1346     
1347     stack< pair<ParseAPI::Function *, int> > callStack;
1348     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1349         calls != cand.con.rend(); ++calls)
1350     {
1351         if(calls->func) {
1352             callStack.push(
1353                std::make_pair(calls->func, calls->stackDepth));
1354         }
1355     }
1356
1357     bool ret = false;
1358     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1359     for( ; ait != cand.active.end(); ++ait) {
1360         ret = ret || p.followCall(callee,callStack,(*ait).first);
1361     }
1362     return ret;
1363 }
1364     
1365
1366
1367 /* ------------------------------------------- */
1368
1369 Address SliceNode::addr() const { 
1370   if (a_)
1371     return a_->addr();
1372   return 0;
1373 }
1374
1375 bool containsCall(ParseAPI::Block *block) {
1376   // We contain a call if the out-edges include
1377   // either a CALL or a CALL_FT edge
1378   const Block::edgelist &targets = block->targets();
1379   Block::edgelist::const_iterator eit = targets.begin();
1380   for (; eit != targets.end(); ++eit) {
1381     ParseAPI::Edge *edge = *eit;
1382     if (edge->type() == CALL) return true;
1383   }
1384   return false;
1385 }
1386
1387 bool containsRet(ParseAPI::Block *block) {
1388   // We contain a call if the out-edges include
1389   // either a CALL or a CALL_FT edge
1390   const Block::edgelist &targets = block->targets();
1391   Block::edgelist::const_iterator eit = targets.begin();
1392   for (; eit != targets.end(); ++eit) {
1393     ParseAPI::Edge *edge = *eit;
1394     if (edge->type() == RET) return true;
1395   }
1396   return false;
1397 }
1398
1399 static void getInsnInstances(ParseAPI::Block *block,
1400                       Slicer::InsnVec &insns) {
1401   Offset off = block->start();
1402   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
1403   if (ptr == NULL) return;
1404   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
1405   while (off < block->end()) {
1406     insns.push_back(std::make_pair(d.decode(), off));
1407     off += insns.back().first->size();
1408   }
1409 }
1410
1411 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
1412   return block->obj()->findFuncByEntry(block->region(), block->start());
1413 }
1414
1415 // Constructor. Takes the initial point we slice from. 
1416
1417 // TODO: make this function-less interprocedural. That would throw the
1418 // stack analysis for a loop, but is generally doable...
1419 Slicer::Slicer(Assignment::Ptr a,
1420                ParseAPI::Block *block,
1421                ParseAPI::Function *func) : 
1422   a_(a),
1423   b_(block),
1424   f_(func),
1425   // Xiaozhu: Temporarily disable stackanalysis, should be able to
1426   // specify it 
1427   converter(false, false) {
1428   df_init_debug();
1429 };
1430
1431 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
1432
1433         // delete cache state
1434   unique_edges_.clear(); 
1435
1436   return sliceInternal(forward, predicates);
1437 }
1438
1439 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
1440   // delete cache state
1441   unique_edges_.clear(); 
1442
1443   return sliceInternal(backward, predicates);
1444 }
1445
1446 bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
1447   StackAnalysis sA(func);
1448
1449   StackAnalysis::Height heightSA = sA.findSP(block, callAddr);
1450
1451   // Ensure that analysis has been performed.
1452
1453   assert(!heightSA.isTop());
1454   
1455   if (heightSA.isBottom()) {
1456     return false;
1457   }
1458   
1459   height = heightSA.height();
1460   
1461   // The height will include the effects of the call
1462   // Should check the region... 
1463
1464   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
1465   //<< std::dec << " " << (int) height << endl;
1466
1467   return true;
1468 }
1469
1470 void Slicer::pushContext(Context &context,
1471                          ParseAPI::Function *callee,
1472                          ParseAPI::Block *callBlock,
1473                          long stackDepth) {
1474   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
1475   assert(context.front().block == NULL);
1476   context.front().block = callBlock;
1477
1478   slicing_cerr << "\t" 
1479                << (context.front().func ? context.front().func->name() : "NULL")
1480                << ", " 
1481                << context.front().stackDepth 
1482                << endl;
1483
1484     context.push_front(ContextElement(callee, stackDepth));
1485 };
1486
1487 void Slicer::popContext(Context &context) {
1488   context.pop_front();
1489
1490   context.front().block = NULL;
1491 }
1492
1493 void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
1494                             AbsRegion &calleeReg,
1495                             long stack_depth,
1496                             ParseAPI::Function *callee) {
1497   if (callerReg.absloc() == Absloc()) {
1498     // Typed, so just keep the same type and call it a day
1499     calleeReg = callerReg;
1500     return;
1501   }
1502   else {
1503     assert(callerReg.type() == Absloc::Unknown);
1504     
1505     const Absloc &callerAloc = callerReg.absloc();
1506     if (callerAloc.type() != Absloc::Stack) {
1507       calleeReg = AbsRegion(callerAloc);
1508     }
1509     else {
1510       if (stack_depth == -1) {
1511         // Oops
1512         calleeReg = AbsRegion(Absloc::Stack);
1513         return;
1514       }
1515       else {
1516         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
1517         //<< " by stack depth " << stack_depth 
1518         //<< " and setting to function " << callee->name() << endl;
1519         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
1520                                      0, // Entry point has region 0 by definition
1521                                      callee));
1522       }
1523     }
1524   }
1525 }
1526
1527 bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
1528   // Did we find a definition of the same abstract region?
1529   // TBD: overlaps ins't quite the right thing here. "contained
1530   // by" would be better, but we need to get the AND/OR
1531   // of abslocs hammered out.
1532   
1533   if (assign->out().type() != Absloc::Unknown) {
1534     // A region assignment can never kill
1535     return false; 
1536   }
1537
1538   if (assign->insn()->getOperation().getID() == e_call && reg.absloc().type() == Absloc::Register) {
1539       const MachRegister &r = reg.absloc().reg();
1540       ABI* abi = ABI::getABI(b_->obj()->cs()->getAddressWidth());
1541       if (abi->getCallWrittenRegisters()[abi->getIndex(r)]) return true;
1542   }
1543   return reg.contains(assign->out());
1544 }
1545
1546 // creates a new node from an element if that node does not yet exist.
1547 // otherwise, it returns the pre-existing node.
1548 SliceNode::Ptr Slicer::createNode(Element const&elem) {
1549   if (created_.find(elem.ptr) != created_.end()) {
1550     return created_[elem.ptr];
1551   }
1552   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
1553   created_[elem.ptr] = newNode;
1554
1555   // mark this node as plausibly being entry/exit.
1556   plausibleNodes.insert(newNode); 
1557   return newNode;
1558 }
1559
1560 std::string SliceNode::format() const {
1561   if (!a_) {
1562     return "<NULL>";
1563   }
1564
1565   stringstream ret;
1566   ret << "(" << a_->format() << "@" <<
1567     f_->name() << ")";
1568   return ret.str();
1569 }
1570
1571 // converts an instruction to a vector of assignments. if this slicer has
1572 // already converted this instruction, this function returns the same
1573 // assignments.
1574 void Slicer::convertInstruction(Instruction::Ptr insn,
1575                                 Address addr,
1576                                 ParseAPI::Function *func,
1577                                 ParseAPI::Block *block,
1578                                 std::vector<Assignment::Ptr> &ret) {
1579   static std::unordered_map<Address, std::vector<Assignment::Ptr> > cache;
1580   if (cache.find(addr) == cache.end()) {
1581   converter.convert(insn,
1582                     addr,
1583                     func,
1584                     block,
1585                     ret);
1586      cache[addr] = ret;
1587   } else ret = cache[addr];
1588   return;
1589 }
1590
1591 void Slicer::getInsns(Location &loc) {
1592
1593
1594   InsnCache::iterator iter = insnCache_.find(loc.block);
1595   if (iter == insnCache_.end()) {
1596     getInsnInstances(loc.block, insnCache_[loc.block]);
1597   }
1598   
1599   loc.current = insnCache_[loc.block].begin();
1600   loc.end = insnCache_[loc.block].end();
1601 }
1602
1603 void Slicer::getInsnsBackward(Location &loc) {
1604     assert(loc.block->start() != (Address) -1); 
1605     InsnCache::iterator iter = insnCache_.find(loc.block);
1606     if (iter == insnCache_.end()) {
1607       getInsnInstances(loc.block, insnCache_[loc.block]);
1608     }
1609
1610     loc.rcurrent = insnCache_[loc.block].rbegin();
1611     loc.rend = insnCache_[loc.block].rend();
1612 }
1613
1614 // inserts an edge from source to target (forward) or target to source
1615 // (backward) if the edge does not yet exist. this is done by converting
1616 // source and target to graph nodes (creating them if they do not exist).
1617 void Slicer::insertPair(Graph::Ptr ret,
1618                         Direction dir,
1619                         Element const&source,
1620                         Element const&target,
1621                         AbsRegion const& data) 
1622 {
1623     SliceNode::Ptr s = createNode(source);
1624     SliceNode::Ptr t = createNode(target);
1625
1626     insertPair(ret, dir, s, t, data);
1627 }
1628
1629 // inserts an edge from source to target (forward) or target to source
1630 // (backward) if the edge does not yet exist.
1631 void Slicer::insertPair(Graph::Ptr ret,
1632                         Direction dir,
1633                         SliceNode::Ptr& s,
1634                         SliceNode::Ptr& t,
1635                         AbsRegion const& data) 
1636 {
1637
1638   EdgeTuple et(s,t,data);
1639   if(unique_edges_.find(et) != unique_edges_.end()) {
1640     unique_edges_[et] += 1;
1641     return;
1642   }
1643   unique_edges_[et] = 1;  
1644
1645   if (dir == forward) {
1646      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1647      ret->insertPair(s, t, e);
1648
1649      // this node is clearly not entry/exit.
1650      plausibleNodes.erase(s);
1651   } else {
1652      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1653      ret->insertPair(t, s, e);
1654
1655      // this node is clearly not entry/exit.
1656      plausibleNodes.erase(s); 
1657   }
1658 }
1659
1660 void
1661 Slicer::widenAll(
1662     Graph::Ptr g,
1663     Direction dir,
1664     SliceFrame const& cand)
1665 {
1666     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1667     for( ; ait != cand.active.end(); ++ait) {
1668         vector<Element> const& eles = (*ait).second;
1669         for(unsigned i=0;i<eles.size();++i)
1670             widen(g,dir,eles[i]);
1671     }
1672 }
1673
1674 void Slicer::widen(Graph::Ptr ret,
1675                    Direction dir,
1676                    Element const&e) {
1677   if (dir == forward) {
1678     ret->insertPair(createNode(e),
1679                     widenNode());
1680     ret->insertExitNode(widenNode());
1681   }
1682   else {
1683     ret->insertPair(widenNode(), createNode(e));
1684     ret->insertEntryNode(widenNode());
1685   }
1686 }
1687
1688 SliceNode::Ptr Slicer::widenNode() {
1689   if (widen_) {
1690     return widen_;
1691   }
1692
1693   widen_ = SliceNode::create(Assignment::Ptr(),
1694                               NULL, NULL);
1695   return widen_;
1696 }
1697
1698 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1699   if (dir == forward) {    
1700     ret->insertExitNode(createNode(e));
1701   }
1702   else {
1703     ret->insertEntryNode(createNode(e));
1704   }
1705 }
1706
1707 void Slicer::fastForward(Location &loc, Address
1708                          addr) {
1709   while ((loc.current != loc.end) &&
1710          (loc.addr() < addr)) {
1711     loc.current++;
1712   }
1713   assert(loc.current != loc.end);
1714   assert(loc.addr() == addr);
1715 }
1716
1717 void Slicer::fastBackward(Location &loc, Address addr) {
1718     while ((loc.rcurrent != loc.rend) &&
1719          (loc.addr() > addr)) {
1720     loc.rcurrent++;
1721   }
1722   assert(loc.rcurrent != loc.rend);
1723   assert(loc.addr() == addr);  
1724 }
1725
1726 // removes unnecessary nodes from the slice graph. this is
1727 // currently mostly ia32/amd64 flags that are written but
1728 // never read. 
1729 void Slicer::cleanGraph(Graph::Ptr ret) {
1730   slicing_cerr << "Cleaning up the graph..." << endl;
1731   // Clean the graph up
1732   
1733   // TODO: make this more efficient by backwards traversing.
1734   // For now, I know that we're generating graphs with tons of
1735   // unnecessary flag sets (which are immediately killed) and so
1736   // we don't have long non-exiting chains, we have "fuzz"
1737   
1738   NodeIterator nbegin, nend;
1739   ret->allNodes(nbegin, nend);
1740   
1741   std::list<Node::Ptr> toDelete;
1742   unsigned numNodes = 0;
1743   for (; nbegin != nend; ++nbegin) {
1744           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1745       numNodes++;
1746       SliceNode::Ptr foozle =
1747           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1748       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1749       if ((*nbegin)->hasOutEdges()) {
1750           slicing_cerr << "\t has out edges, leaving in" << endl;
1751           continue;
1752       }
1753
1754       // don't remove entry/exit nodes.
1755       if (ret->isEntryNode(*nbegin) || ret->isExitNode(*nbegin)) {
1756           continue;
1757       }
1758
1759       // mark non-flags nodes as exit nodes. these nodes are likely
1760       // relevant to the slice and should not be deleted. only delete 
1761       // flag nodes. this should stop the over-deleting by this
1762       // function, but this is a fairly ugly way of doing it. 
1763       const Absloc& abs = foozle->a_->out().absloc();
1764       if (abs.type() == Absloc::Register && 
1765                         (abs.reg().getArchitecture() == Arch_x86 
1766                          || abs.reg().getArchitecture() == Arch_x86_64) && 
1767                         (abs.reg().getBaseRegister() & x86::FLAG) == x86::FLAG) {
1768           slicing_cerr << "\t deleting" << endl;
1769           toDelete.push_back(*nbegin);
1770       } else {
1771           ret->markAsExitNode(foozle);
1772       }
1773   }
1774
1775   for (std::list<Node::Ptr>::iterator tmp =
1776            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1777       ret->deleteNode(*tmp);
1778   }
1779   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1780 }
1781
1782 // promotes nodes in the slice graph to termination nodes.
1783 // essentially, the slicer maintains a set of nodes that 
1784 // may be entry/exit nodes for the backwards/fowards case.
1785 // this function removes the nodes from the set, and 
1786 // marks them in the graph as true entry/exit nodes.
1787 // in the forward case, the entry node is a single node,
1788 // the assignment from which the slice began. in the backward
1789 // case, this node is the single exit node. exit nodes in the
1790 // forward case are definitions that are still live at function
1791 // exit. entry nodes in the backward case are uses for which the
1792 // definition lies outside the function (before entry) or move
1793 // instructions where one operand is a literal.
1794 void Slicer::promotePlausibleNodes(GraphPtr g, Direction d) {
1795     // note: it would be better to reuse some other
1796     // functions here, but none of them quite use 
1797     // the interface we need here.
1798     if (d == forward) {
1799         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1800              first != last; ++first) {
1801             g->markAsExitNode(*first);
1802         }
1803     } else {
1804         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1805              first != last; ++first) {
1806             g->markAsEntryNode(*first);
1807         }
1808     }
1809     plausibleNodes.clear();
1810 }
1811
1812 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1813                                    Direction dir) {
1814   return ((dir == forward) ? e->trg() : e->src());
1815 }
1816
1817 bool Slicer::isWidenNode(Node::Ptr n) {
1818   SliceNode::Ptr foozle =
1819     boost::dynamic_pointer_cast<SliceNode>(n);
1820   if (!foozle) return false;
1821   if (!foozle->assign()) return true;
1822   return false;
1823 }
1824
1825 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1826   if (dir == forward) {
1827     // Entry node
1828     ret->insertEntryNode(aP);
1829   }
1830   else {
1831     ret->insertExitNode(aP);
1832   }
1833 }
1834
1835 // creates the initial slice frame and initializes instance variables.
1836 void Slicer::constructInitialFrame(
1837     Direction dir,
1838     SliceFrame & initFrame)
1839 {
1840     Instruction::Ptr init_instruction;
1841     initFrame.con.push_front(ContextElement(f_));
1842     initFrame.loc = Location(f_,b_);
1843
1844     // increment iterators to initial instruction. 
1845     if(dir == forward) {
1846         initFrame.loc.fwd = true;
1847         getInsns(initFrame.loc);
1848         fastForward(initFrame.loc, a_->addr());
1849         init_instruction = initFrame.loc.current->first;
1850     } else {
1851         initFrame.loc.fwd = false;
1852         getInsnsBackward(initFrame.loc);
1853         fastBackward(initFrame.loc, a_->addr());
1854         init_instruction = initFrame.loc.rcurrent->first;
1855     }
1856
1857     // reconstruct initial assignment. the initial assignment was created
1858     // by a different converter, and thus if the instruction is visited
1859     // more than once by the slicer, the assignment will be recreated
1860     // instead of coming out of cache. this results in duplicated graph
1861     // nodes. 
1862     std::vector<Assignment::Ptr> assigns;
1863     convertInstruction(init_instruction, a_->addr(), f_, b_, assigns);
1864     for (auto first = assigns.begin(), last = assigns.end(); first != last; ++first) {
1865         if ((*first)->out() == a_->out()) { a_ = *first; break; }
1866     }
1867
1868     if(dir == forward) {
1869         Element oe(b_,f_,a_->out(),a_);
1870         initFrame.active[a_->out()].push_back(oe);
1871     } else {
1872         vector<AbsRegion> & inputs = a_->inputs();
1873         vector<AbsRegion>::iterator iit = inputs.begin();
1874         for ( ; iit != inputs.end(); ++iit) {
1875             Element ie(b_,f_,*iit,a_);
1876             initFrame.active[*iit].push_back(ie);
1877         }
1878     }
1879 }
1880
1881 void
1882 Slicer::DefCache::merge(Slicer::DefCache const& o)
1883 {
1884     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1885     for( ; oit != o.defmap.end(); ++oit) {
1886         AbsRegion const& r = oit->first;
1887         set<Def> const& s = oit->second;
1888         defmap[r].insert(s.begin(),s.end());
1889     }
1890 }
1891
1892 void
1893 Slicer::DefCache::replace(Slicer::DefCache const& o)
1894 {   
1895     // XXX if o.defmap[region] is empty set, remove that entry
1896     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1897     for( ; oit != o.defmap.end(); ++oit) {
1898         if(!(*oit).second.empty())
1899             defmap[(*oit).first] = (*oit).second;
1900         else
1901             defmap.erase((*oit).first);
1902     }
1903 }
1904
1905 void
1906 Slicer::DefCache::print() const {
1907     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1908     for( ; it !=defmap.end(); ++it) {
1909         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1910         set<Def> const& defs = (*it).second;
1911         set<Def>::const_iterator dit = defs.begin();
1912         for( ; dit != defs.end(); ++dit) {
1913             slicing_printf("\t\t\t<%s,%s>\n",
1914                 (*dit).ele.ptr->format().c_str(),
1915                 (*dit).data.format().c_str());
1916         }
1917     }
1918 }
1919
1920 // merges all single caches that have occured single addr in the
1921 // recursion into the appropriate unified caches.
1922 void Slicer::mergeRecursiveCaches(std::map<Address, DefCache>& single, 
1923                                   std::map<Address, DefCache>& unified, Address addr) {
1924
1925
1926     for (auto first = addrStack.rbegin(), last = addrStack.rend();
1927             first != last; ++first) {
1928         unified[*first].replace(single[*first]);
1929         auto next = first + 1;
1930         if (next != last) {
1931             unified[*next].merge(unified[*first]);
1932         }
1933     }
1934 }
1935