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