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