CANNOT use a global cache to store converted assignments based on their addresses
[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 // Note that we CANNOT use a global cache based on the address
1575 // of the instruction to convert because the block that contains
1576 // the instructino may change during parsing.
1577 void Slicer::convertInstruction(Instruction::Ptr insn,
1578                                 Address addr,
1579                                 ParseAPI::Function *func,
1580                                 ParseAPI::Block *block,
1581                                 std::vector<Assignment::Ptr> &ret) {
1582   converter.convert(insn,
1583                     addr,
1584                     func,
1585                     block,
1586                     ret);
1587   return;
1588 }
1589
1590 void Slicer::getInsns(Location &loc) {
1591
1592
1593   InsnCache::iterator iter = insnCache_.find(loc.block);
1594   if (iter == insnCache_.end()) {
1595     getInsnInstances(loc.block, insnCache_[loc.block]);
1596   }
1597   
1598   loc.current = insnCache_[loc.block].begin();
1599   loc.end = insnCache_[loc.block].end();
1600 }
1601
1602 void Slicer::getInsnsBackward(Location &loc) {
1603     assert(loc.block->start() != (Address) -1); 
1604     InsnCache::iterator iter = insnCache_.find(loc.block);
1605     if (iter == insnCache_.end()) {
1606       getInsnInstances(loc.block, insnCache_[loc.block]);
1607     }
1608
1609     loc.rcurrent = insnCache_[loc.block].rbegin();
1610     loc.rend = insnCache_[loc.block].rend();
1611 }
1612
1613 // inserts an edge from source to target (forward) or target to source
1614 // (backward) if the edge does not yet exist. this is done by converting
1615 // source and target to graph nodes (creating them if they do not exist).
1616 void Slicer::insertPair(Graph::Ptr ret,
1617                         Direction dir,
1618                         Element const&source,
1619                         Element const&target,
1620                         AbsRegion const& data) 
1621 {
1622     SliceNode::Ptr s = createNode(source);
1623     SliceNode::Ptr t = createNode(target);
1624
1625     insertPair(ret, dir, s, t, data);
1626 }
1627
1628 // inserts an edge from source to target (forward) or target to source
1629 // (backward) if the edge does not yet exist.
1630 void Slicer::insertPair(Graph::Ptr ret,
1631                         Direction dir,
1632                         SliceNode::Ptr& s,
1633                         SliceNode::Ptr& t,
1634                         AbsRegion const& data) 
1635 {
1636
1637   EdgeTuple et(s,t,data);
1638   if(unique_edges_.find(et) != unique_edges_.end()) {
1639     unique_edges_[et] += 1;
1640     return;
1641   }
1642   unique_edges_[et] = 1;  
1643
1644   if (dir == forward) {
1645      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1646      ret->insertPair(s, t, e);
1647
1648      // this node is clearly not entry/exit.
1649      plausibleNodes.erase(s);
1650   } else {
1651      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1652      ret->insertPair(t, s, e);
1653
1654      // this node is clearly not entry/exit.
1655      plausibleNodes.erase(s); 
1656   }
1657 }
1658
1659 void
1660 Slicer::widenAll(
1661     Graph::Ptr g,
1662     Direction dir,
1663     SliceFrame const& cand)
1664 {
1665     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1666     for( ; ait != cand.active.end(); ++ait) {
1667         vector<Element> const& eles = (*ait).second;
1668         for(unsigned i=0;i<eles.size();++i)
1669             widen(g,dir,eles[i]);
1670     }
1671 }
1672
1673 void Slicer::widen(Graph::Ptr ret,
1674                    Direction dir,
1675                    Element const&e) {
1676   if (dir == forward) {
1677     ret->insertPair(createNode(e),
1678                     widenNode());
1679     ret->insertExitNode(widenNode());
1680   }
1681   else {
1682     ret->insertPair(widenNode(), createNode(e));
1683     ret->insertEntryNode(widenNode());
1684   }
1685 }
1686
1687 SliceNode::Ptr Slicer::widenNode() {
1688   if (widen_) {
1689     return widen_;
1690   }
1691
1692   widen_ = SliceNode::create(Assignment::Ptr(),
1693                               NULL, NULL);
1694   return widen_;
1695 }
1696
1697 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1698   if (dir == forward) {    
1699     ret->insertExitNode(createNode(e));
1700   }
1701   else {
1702     ret->insertEntryNode(createNode(e));
1703   }
1704 }
1705
1706 void Slicer::fastForward(Location &loc, Address
1707                          addr) {
1708   while ((loc.current != loc.end) &&
1709          (loc.addr() < addr)) {
1710     loc.current++;
1711   }
1712   assert(loc.current != loc.end);
1713   assert(loc.addr() == addr);
1714 }
1715
1716 void Slicer::fastBackward(Location &loc, Address addr) {
1717     while ((loc.rcurrent != loc.rend) &&
1718          (loc.addr() > addr)) {
1719     loc.rcurrent++;
1720   }
1721   assert(loc.rcurrent != loc.rend);
1722   assert(loc.addr() == addr);  
1723 }
1724
1725 // removes unnecessary nodes from the slice graph. this is
1726 // currently mostly ia32/amd64 flags that are written but
1727 // never read. 
1728 void Slicer::cleanGraph(Graph::Ptr ret) {
1729   slicing_cerr << "Cleaning up the graph..." << endl;
1730   // Clean the graph up
1731   
1732   // TODO: make this more efficient by backwards traversing.
1733   // For now, I know that we're generating graphs with tons of
1734   // unnecessary flag sets (which are immediately killed) and so
1735   // we don't have long non-exiting chains, we have "fuzz"
1736   
1737   NodeIterator nbegin, nend;
1738   ret->allNodes(nbegin, nend);
1739   
1740   std::list<Node::Ptr> toDelete;
1741   unsigned numNodes = 0;
1742   for (; nbegin != nend; ++nbegin) {
1743           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1744       numNodes++;
1745       SliceNode::Ptr foozle =
1746           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1747       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1748       if ((*nbegin)->hasOutEdges()) {
1749           slicing_cerr << "\t has out edges, leaving in" << endl;
1750           continue;
1751       }
1752
1753       // don't remove entry/exit nodes.
1754       if (ret->isEntryNode(*nbegin) || ret->isExitNode(*nbegin)) {
1755           continue;
1756       }
1757
1758       // mark non-flags nodes as exit nodes. these nodes are likely
1759       // relevant to the slice and should not be deleted. only delete 
1760       // flag nodes. this should stop the over-deleting by this
1761       // function, but this is a fairly ugly way of doing it. 
1762       const Absloc& abs = foozle->a_->out().absloc();
1763       if (abs.type() == Absloc::Register && 
1764                         (abs.reg().getArchitecture() == Arch_x86 
1765                          || abs.reg().getArchitecture() == Arch_x86_64) && 
1766                         (abs.reg().getBaseRegister() & x86::FLAG) == x86::FLAG) {
1767           slicing_cerr << "\t deleting" << endl;
1768           toDelete.push_back(*nbegin);
1769       } else {
1770           ret->markAsExitNode(foozle);
1771       }
1772   }
1773
1774   for (std::list<Node::Ptr>::iterator tmp =
1775            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1776       ret->deleteNode(*tmp);
1777   }
1778   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1779 }
1780
1781 // promotes nodes in the slice graph to termination nodes.
1782 // essentially, the slicer maintains a set of nodes that 
1783 // may be entry/exit nodes for the backwards/fowards case.
1784 // this function removes the nodes from the set, and 
1785 // marks them in the graph as true entry/exit nodes.
1786 // in the forward case, the entry node is a single node,
1787 // the assignment from which the slice began. in the backward
1788 // case, this node is the single exit node. exit nodes in the
1789 // forward case are definitions that are still live at function
1790 // exit. entry nodes in the backward case are uses for which the
1791 // definition lies outside the function (before entry) or move
1792 // instructions where one operand is a literal.
1793 void Slicer::promotePlausibleNodes(GraphPtr g, Direction d) {
1794     // note: it would be better to reuse some other
1795     // functions here, but none of them quite use 
1796     // the interface we need here.
1797     if (d == forward) {
1798         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1799              first != last; ++first) {
1800             g->markAsExitNode(*first);
1801         }
1802     } else {
1803         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1804              first != last; ++first) {
1805             g->markAsEntryNode(*first);
1806         }
1807     }
1808     plausibleNodes.clear();
1809 }
1810
1811 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1812                                    Direction dir) {
1813   return ((dir == forward) ? e->trg() : e->src());
1814 }
1815
1816 bool Slicer::isWidenNode(Node::Ptr n) {
1817   SliceNode::Ptr foozle =
1818     boost::dynamic_pointer_cast<SliceNode>(n);
1819   if (!foozle) return false;
1820   if (!foozle->assign()) return true;
1821   return false;
1822 }
1823
1824 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1825   if (dir == forward) {
1826     // Entry node
1827     ret->insertEntryNode(aP);
1828   }
1829   else {
1830     ret->insertExitNode(aP);
1831   }
1832 }
1833
1834 // creates the initial slice frame and initializes instance variables.
1835 void Slicer::constructInitialFrame(
1836     Direction dir,
1837     SliceFrame & initFrame)
1838 {
1839     Instruction::Ptr init_instruction;
1840     initFrame.con.push_front(ContextElement(f_));
1841     initFrame.loc = Location(f_,b_);
1842
1843     // increment iterators to initial instruction. 
1844     if(dir == forward) {
1845         initFrame.loc.fwd = true;
1846         getInsns(initFrame.loc);
1847         fastForward(initFrame.loc, a_->addr());
1848         init_instruction = initFrame.loc.current->first;
1849     } else {
1850         initFrame.loc.fwd = false;
1851         getInsnsBackward(initFrame.loc);
1852         fastBackward(initFrame.loc, a_->addr());
1853         init_instruction = initFrame.loc.rcurrent->first;
1854     }
1855
1856     // reconstruct initial assignment. the initial assignment was created
1857     // by a different converter, and thus if the instruction is visited
1858     // more than once by the slicer, the assignment will be recreated
1859     // instead of coming out of cache. this results in duplicated graph
1860     // nodes. 
1861     std::vector<Assignment::Ptr> assigns;
1862     convertInstruction(init_instruction, a_->addr(), f_, b_, assigns);
1863     for (auto first = assigns.begin(), last = assigns.end(); first != last; ++first) {
1864         if ((*first)->out() == a_->out()) { a_ = *first; break; }
1865     }
1866
1867     if(dir == forward) {
1868         Element oe(b_,f_,a_->out(),a_);
1869         initFrame.active[a_->out()].push_back(oe);
1870     } else {
1871         vector<AbsRegion> & inputs = a_->inputs();
1872         vector<AbsRegion>::iterator iit = inputs.begin();
1873         for ( ; iit != inputs.end(); ++iit) {
1874             Element ie(b_,f_,*iit,a_);
1875             initFrame.active[*iit].push_back(ie);
1876         }
1877     }
1878 }
1879
1880 void
1881 Slicer::DefCache::merge(Slicer::DefCache const& o)
1882 {
1883     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1884     for( ; oit != o.defmap.end(); ++oit) {
1885         AbsRegion const& r = oit->first;
1886         set<Def> const& s = oit->second;
1887         defmap[r].insert(s.begin(),s.end());
1888     }
1889 }
1890
1891 void
1892 Slicer::DefCache::replace(Slicer::DefCache const& o)
1893 {   
1894     // XXX if o.defmap[region] is empty set, remove that entry
1895     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1896     for( ; oit != o.defmap.end(); ++oit) {
1897         if(!(*oit).second.empty())
1898             defmap[(*oit).first] = (*oit).second;
1899         else
1900             defmap.erase((*oit).first);
1901     }
1902 }
1903
1904 void
1905 Slicer::DefCache::print() const {
1906     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1907     for( ; it !=defmap.end(); ++it) {
1908         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1909         set<Def> const& defs = (*it).second;
1910         set<Def>::const_iterator dit = defs.begin();
1911         for( ; dit != defs.end(); ++dit) {
1912             slicing_printf("\t\t\t<%s,%s>\n",
1913                 (*dit).ele.ptr->format().c_str(),
1914                 (*dit).data.format().c_str());
1915         }
1916     }
1917 }
1918
1919 // merges all single caches that have occured single addr in the
1920 // recursion into the appropriate unified caches.
1921 void Slicer::mergeRecursiveCaches(std::map<Address, DefCache>& single, 
1922                                   std::map<Address, DefCache>& unified, Address addr) {
1923
1924
1925     for (auto first = addrStack.rbegin(), last = addrStack.rend();
1926             first != last; ++first) {
1927         unified[*first].replace(single[*first]);
1928         auto next = first + 1;
1929         if (next != last) {
1930             unified[*next].merge(unified[*first]);
1931         }
1932     }
1933 }
1934