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