1. Refactor code of reading contents from jump tables and determining jump target...
[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) && p.modifyCurrentFrame(initFrame, ret)) {
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 p.modifyCurrentFrame(cand, g);
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             cur.active[AbsRegion(Absloc(MachRegister::getPC(cur.loc.block->obj()->cs()->getArch())))] = newE;
1109             slicing_printf("\tadding tracking ip for control flow information ");
1110         }
1111     }
1112     return true;
1113 }
1114
1115 /* ----------------- backwards slicing implementations ------------------ */
1116
1117 bool
1118 Slicer::handleCallBackward(
1119     Predicates & p,
1120     SliceFrame const& cand,
1121     vector<SliceFrame> & newCands,
1122     ParseAPI::Edge * e,
1123     bool & /* err */)
1124 {
1125     // We don't know which function the caller block belongs to,
1126     // so check each possibility against the predicate.
1127     //
1128     // XXX   this suffers the same problem as followCall in the forward
1129     //       case; the predicates test against only a single abstract
1130     //       region. What we do here is to build up mappings from
1131     //       function paths (that will be followed) to sets of abstract
1132     //       regions, then create SliceFrames with these sets.
1133
1134     map<ParseAPI::Function *, SliceFrame::ActiveMap > fmap;
1135
1136     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1137     for( ; ait != cand.active.end(); ++ait) {
1138         vector<ParseAPI::Function *> follow = 
1139             followCallBackward(p,cand,(*ait).first,e->src());
1140         for(unsigned j=0;j<follow.size();++j) {
1141             fmap[follow[j]].insert(*ait);
1142         }
1143     }
1144
1145     map<ParseAPI::Function *, SliceFrame::ActiveMap >::iterator mit = 
1146         fmap.begin();
1147     for( ; mit != fmap.end(); ++mit) {
1148         ParseAPI::Function * f = (*mit).first;
1149         SliceFrame::ActiveMap & act = (*mit).second;
1150     
1151         SliceFrame nf(cand.loc,cand.con);
1152         nf.active = act;
1153
1154         nf.con.push_back(ContextElement(f));
1155         nf.loc.block = e->src();
1156         nf.loc.func = f;
1157
1158         // pop context & adjust AbsRegions
1159         if(!handleCallDetailsBackward(nf)) {
1160             // FIXME I have preserved this behavior (returning false if
1161             //       the current frame can't be adjusted). It seems to
1162             //       me that we ought to set err = true and continue
1163             //       processing the rest of the call edges.
1164             //
1165             //       This issue needs review by somebody knowledgeable
1166             //       about the slicer.
1167             return false;
1168         }
1169
1170         getInsnsBackward(nf.loc);
1171         newCands.push_back(nf);
1172     } 
1173     return true;
1174 }
1175
1176 /*
1177  * FIXME egregious copying
1178  */
1179 vector<ParseAPI::Function *>
1180 Slicer::followCallBackward(
1181     Predicates & p,
1182     SliceFrame const& cand,
1183     AbsRegion const& reg,
1184     ParseAPI::Block * caller_block)
1185 {
1186     stack< pair<ParseAPI::Function *, int> > callStack;  
1187     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1188         calls != cand.con.rend(); ++calls)
1189     {
1190         if(calls->func) {
1191             callStack.push(
1192                std::make_pair(calls->func, calls->stackDepth));
1193         }
1194     }
1195     return p.followCallBackward(caller_block, callStack, reg);
1196 }
1197
1198 bool
1199 Slicer::handleCallDetailsBackward(
1200     SliceFrame & cur)
1201 {
1202     ParseAPI::Block * callBlock = cur.loc.block;
1203     ParseAPI::Function * caller = cur.loc.func;
1204
1205     Address callBlockLastInsn = callBlock->lastInsnAddr();
1206
1207     long stack_depth;
1208     if(!getStackDepth(caller, callBlock, callBlockLastInsn,stack_depth)) {
1209         return false;
1210     }
1211
1212     popContext(cur.con);
1213     assert(!cur.con.empty());
1214
1215
1216     slicing_printf("\t%s, %d\n",
1217         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1218         cur.con.front().stackDepth);
1219
1220     // Transform the active abstract regions
1221     shiftAllAbsRegions(cur,-1*stack_depth,caller);
1222
1223     return true;
1224 }
1225     
1226 bool
1227 Slicer::handleReturnBackward(
1228     Predicates & p,
1229     SliceFrame const& cand,
1230     SliceFrame & newCand,
1231     ParseAPI::Edge * e,
1232     bool & err)
1233 {
1234     ParseAPI::Block * callee = e->src();
1235
1236     // cons up a call stack for the call associated
1237     // with this return and ask the predicates whether
1238     // they would have come down this call.
1239     //
1240     // FIXME the issue of predicates evaluating only a
1241     //       single abstract region applies here as well;
1242     //       see comments in handleCall and handleCallBackward
1243
1244     if(followReturn(p,cand,callee)) {
1245         // XXX it is not clear to me why a null callee is an error here
1246         //     but not if followReturn returns false FIXME
1247         if(!callee) {
1248             err = true;
1249             return false;
1250         }
1251
1252         newCand = cand;
1253         newCand.loc.block = callee;
1254         newCand.loc.func = getEntryFunc(callee);
1255         getInsnsBackward(newCand.loc);
1256
1257         if(!handleReturnDetailsBackward(newCand,cand.loc.block)) {
1258             err = true;
1259             return false;
1260         }
1261         return true;
1262     } 
1263     return false;
1264 }
1265
1266 bool
1267 Slicer::handleReturnDetailsBackward(
1268     SliceFrame & cur,
1269     ParseAPI::Block * caller_block)
1270 {
1271     ParseAPI::Function * caller = cur.con.front().func;
1272     ParseAPI::Function * callee = cur.loc.func;
1273
1274     long stack_depth;
1275     if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
1276         return false;
1277     }
1278     
1279     pushContext(cur.con, callee, caller_block, stack_depth);
1280
1281     // Transform the active abstract regions
1282     shiftAllAbsRegions(cur,stack_depth,caller);
1283
1284     return true; 
1285 }
1286
1287 bool
1288 Slicer::followReturn(
1289     Predicates & p,
1290     SliceFrame const& cand,
1291     ParseAPI::Block * source)
1292 {
1293     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1294     
1295     stack< pair<ParseAPI::Function *, int> > callStack;
1296     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1297         calls != cand.con.rend(); ++calls)
1298     {
1299         if(calls->func) {
1300             callStack.push(
1301                std::make_pair(calls->func, calls->stackDepth));
1302         }
1303     }
1304
1305     bool ret = false;
1306     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1307     for( ; ait != cand.active.end(); ++ait) {
1308         ret = ret || p.followCall(callee,callStack,(*ait).first);
1309     }
1310     return ret;
1311 }
1312     
1313
1314
1315 /* ------------------------------------------- */
1316
1317 Address SliceNode::addr() const { 
1318   if (a_)
1319     return a_->addr();
1320   return 0;
1321 }
1322
1323 bool containsCall(ParseAPI::Block *block) {
1324   // We contain a call if the out-edges include
1325   // either a CALL or a CALL_FT edge
1326   const Block::edgelist &targets = block->targets();
1327   Block::edgelist::const_iterator eit = targets.begin();
1328   for (; eit != targets.end(); ++eit) {
1329     ParseAPI::Edge *edge = *eit;
1330     if (edge->type() == CALL) return true;
1331   }
1332   return false;
1333 }
1334
1335 bool containsRet(ParseAPI::Block *block) {
1336   // We contain a call if the out-edges include
1337   // either a CALL or a CALL_FT edge
1338   const Block::edgelist &targets = block->targets();
1339   Block::edgelist::const_iterator eit = targets.begin();
1340   for (; eit != targets.end(); ++eit) {
1341     ParseAPI::Edge *edge = *eit;
1342     if (edge->type() == RET) return true;
1343   }
1344   return false;
1345 }
1346
1347 static void getInsnInstances(ParseAPI::Block *block,
1348                       Slicer::InsnVec &insns) {
1349   Offset off = block->start();
1350   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
1351   if (ptr == NULL) return;
1352   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
1353   while (off < block->end()) {
1354     insns.push_back(std::make_pair(d.decode(), off));
1355     off += insns.back().first->size();
1356   }
1357 }
1358
1359 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
1360   return block->obj()->findFuncByEntry(block->region(), block->start());
1361 }
1362
1363 // Constructor. Takes the initial point we slice from. 
1364
1365 // TODO: make this function-less interprocedural. That would throw the
1366 // stack analysis for a loop, but is generally doable...
1367 Slicer::Slicer(Assignment::Ptr a,
1368                ParseAPI::Block *block,
1369                ParseAPI::Function *func,
1370                bool cache,
1371                bool stackAnalysis) : 
1372   a_(a),
1373   b_(block),
1374   f_(func),
1375   converter(cache, stackAnalysis) {
1376   df_init_debug();
1377 };
1378
1379 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
1380
1381         // delete cache state
1382   unique_edges_.clear(); 
1383
1384   return sliceInternal(forward, predicates);
1385 }
1386
1387 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
1388   // delete cache state
1389   unique_edges_.clear(); 
1390
1391   return sliceInternal(backward, predicates);
1392 }
1393
1394 bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
1395   StackAnalysis sA(func);
1396
1397   StackAnalysis::Height heightSA = sA.findSP(block, callAddr);
1398
1399   // Ensure that analysis has been performed.
1400
1401   assert(!heightSA.isTop());
1402   
1403   if (heightSA.isBottom()) {
1404     return false;
1405   }
1406   
1407   height = heightSA.height();
1408   
1409   // The height will include the effects of the call
1410   // Should check the region... 
1411
1412   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
1413   //<< std::dec << " " << (int) height << endl;
1414
1415   return true;
1416 }
1417
1418 void Slicer::pushContext(Context &context,
1419                          ParseAPI::Function *callee,
1420                          ParseAPI::Block *callBlock,
1421                          long stackDepth) {
1422   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
1423   assert(context.front().block == NULL);
1424   context.front().block = callBlock;
1425
1426   slicing_cerr << "\t" 
1427                << (context.front().func ? context.front().func->name() : "NULL")
1428                << ", " 
1429                << context.front().stackDepth 
1430                << endl;
1431
1432     context.push_front(ContextElement(callee, stackDepth));
1433 };
1434
1435 void Slicer::popContext(Context &context) {
1436   context.pop_front();
1437
1438   context.front().block = NULL;
1439 }
1440
1441 void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
1442                             AbsRegion &calleeReg,
1443                             long stack_depth,
1444                             ParseAPI::Function *callee) {
1445   if (callerReg.absloc() == Absloc()) {
1446     // Typed, so just keep the same type and call it a day
1447     calleeReg = callerReg;
1448     return;
1449   }
1450   else {
1451     assert(callerReg.type() == Absloc::Unknown);
1452     
1453     const Absloc &callerAloc = callerReg.absloc();
1454     if (callerAloc.type() != Absloc::Stack) {
1455       calleeReg = AbsRegion(callerAloc);
1456     }
1457     else {
1458       if (stack_depth == -1) {
1459         // Oops
1460         calleeReg = AbsRegion(Absloc::Stack);
1461         return;
1462       }
1463       else {
1464         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
1465         //<< " by stack depth " << stack_depth 
1466         //<< " and setting to function " << callee->name() << endl;
1467         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
1468                                      0, // Entry point has region 0 by definition
1469                                      callee));
1470       }
1471     }
1472   }
1473 }
1474
1475 bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
1476   // Did we find a definition of the same abstract region?
1477   // TBD: overlaps ins't quite the right thing here. "contained
1478   // by" would be better, but we need to get the AND/OR
1479   // of abslocs hammered out.
1480   
1481   if (assign->out().type() != Absloc::Unknown) {
1482     // A region assignment can never kill
1483     return false; 
1484   }
1485
1486   if (assign->insn()->getOperation().getID() == e_call && reg.absloc().type() == Absloc::Register) {
1487       MachRegister r = reg.absloc().reg();
1488       ABI* abi = ABI::getABI(b_->obj()->cs()->getAddressWidth());
1489       int index = abi->getIndex(r);
1490       if (index >= 0)
1491           if (abi->getCallWrittenRegisters()[abi->getIndex(r)] && r != x86_64::r11) return true;
1492   }
1493   return reg.contains(assign->out());
1494 }
1495
1496 // creates a new node from an element if that node does not yet exist.
1497 // otherwise, it returns the pre-existing node.
1498 SliceNode::Ptr Slicer::createNode(Element const&elem) {
1499   if (created_.find(elem.ptr) != created_.end()) {
1500     return created_[elem.ptr];
1501   }
1502   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
1503   created_[elem.ptr] = newNode;
1504
1505   // mark this node as plausibly being entry/exit.
1506   plausibleNodes.insert(newNode); 
1507   return newNode;
1508 }
1509
1510 std::string SliceNode::format() const {
1511   if (!a_) {
1512     return "<NULL>";
1513   }
1514
1515   stringstream ret;
1516   ret << "(" << a_->format() << "@" <<
1517     f_->name() << ")";
1518   return ret.str();
1519 }
1520
1521 // converts an instruction to a vector of assignments. if this slicer has
1522 // already converted this instruction, this function returns the same
1523 // assignments.
1524 // Note that we CANNOT use a global cache based on the address
1525 // of the instruction to convert because the block that contains
1526 // the instructino may change during parsing.
1527 void Slicer::convertInstruction(Instruction::Ptr insn,
1528                                 Address addr,
1529                                 ParseAPI::Function *func,
1530                                 ParseAPI::Block *block,
1531                                 std::vector<Assignment::Ptr> &ret) {
1532   converter.convert(insn,
1533                     addr,
1534                     func,
1535                     block,
1536                     ret);
1537   return;
1538 }
1539
1540 void Slicer::getInsns(Location &loc) {
1541
1542
1543   InsnCache::iterator iter = insnCache_.find(loc.block);
1544   if (iter == insnCache_.end()) {
1545     getInsnInstances(loc.block, insnCache_[loc.block]);
1546   }
1547   
1548   loc.current = insnCache_[loc.block].begin();
1549   loc.end = insnCache_[loc.block].end();
1550 }
1551
1552 void Slicer::getInsnsBackward(Location &loc) {
1553     assert(loc.block->start() != (Address) -1); 
1554     InsnCache::iterator iter = insnCache_.find(loc.block);
1555     if (iter == insnCache_.end()) {
1556       getInsnInstances(loc.block, insnCache_[loc.block]);
1557     }
1558
1559     loc.rcurrent = insnCache_[loc.block].rbegin();
1560     loc.rend = insnCache_[loc.block].rend();
1561 }
1562
1563 // inserts an edge from source to target (forward) or target to source
1564 // (backward) if the edge does not yet exist. this is done by converting
1565 // source and target to graph nodes (creating them if they do not exist).
1566 void Slicer::insertPair(Graph::Ptr ret,
1567                         Direction dir,
1568                         Element const&source,
1569                         Element const&target,
1570                         AbsRegion const& data) 
1571 {
1572     SliceNode::Ptr s = createNode(source);
1573     SliceNode::Ptr t = createNode(target);
1574
1575     insertPair(ret, dir, s, t, data);
1576 }
1577
1578 // inserts an edge from source to target (forward) or target to source
1579 // (backward) if the edge does not yet exist.
1580 void Slicer::insertPair(Graph::Ptr ret,
1581                         Direction dir,
1582                         SliceNode::Ptr& s,
1583                         SliceNode::Ptr& t,
1584                         AbsRegion const& data) 
1585 {
1586
1587   EdgeTuple et(s,t,data);
1588   if(unique_edges_.find(et) != unique_edges_.end()) {
1589     unique_edges_[et] += 1;
1590     return;
1591   }
1592   unique_edges_[et] = 1;  
1593
1594   if (dir == forward) {
1595      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1596      ret->insertPair(s, t, e);
1597
1598      // this node is clearly not entry/exit.
1599      plausibleNodes.erase(s);
1600   } else {
1601      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1602      ret->insertPair(t, s, e);
1603
1604      // this node is clearly not entry/exit.
1605      plausibleNodes.erase(s); 
1606   }
1607 }
1608
1609 void
1610 Slicer::widenAll(
1611     Graph::Ptr g,
1612     Direction dir,
1613     SliceFrame const& cand)
1614 {
1615     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1616     for( ; ait != cand.active.end(); ++ait) {
1617         vector<Element> const& eles = (*ait).second;
1618         for(unsigned i=0;i<eles.size();++i)
1619             widen(g,dir,eles[i]);
1620     }
1621 }
1622
1623 void Slicer::widen(Graph::Ptr ret,
1624                    Direction dir,
1625                    Element const&e) {
1626   if (dir == forward) {
1627     ret->insertPair(createNode(e),
1628                     widenNode());
1629     ret->insertExitNode(widenNode());
1630   }
1631   else {
1632     ret->insertPair(widenNode(), createNode(e));
1633     ret->insertEntryNode(widenNode());
1634   }
1635 }
1636
1637 SliceNode::Ptr Slicer::widenNode() {
1638   if (widen_) {
1639     return widen_;
1640   }
1641
1642   widen_ = SliceNode::create(Assignment::Ptr(),
1643                               NULL, NULL);
1644   return widen_;
1645 }
1646
1647 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1648   if (dir == forward) {    
1649     ret->insertExitNode(createNode(e));
1650   }
1651   else {
1652     ret->insertEntryNode(createNode(e));
1653   }
1654 }
1655
1656 void Slicer::fastForward(Location &loc, Address
1657                          addr) {
1658   while ((loc.current != loc.end) &&
1659          (loc.addr() < addr)) {
1660     loc.current++;
1661   }
1662   assert(loc.current != loc.end);
1663   assert(loc.addr() == addr);
1664 }
1665
1666 void Slicer::fastBackward(Location &loc, Address addr) {
1667     while ((loc.rcurrent != loc.rend) &&
1668          (loc.addr() > addr)) {
1669     loc.rcurrent++;
1670   }
1671   assert(loc.rcurrent != loc.rend);
1672   assert(loc.addr() == addr);  
1673 }
1674
1675 // removes unnecessary nodes from the slice graph. this is
1676 // currently mostly ia32/amd64 flags that are written but
1677 // never read. 
1678 void Slicer::cleanGraph(Graph::Ptr ret) {
1679   slicing_cerr << "Cleaning up the graph..." << endl;
1680   // Clean the graph up
1681   
1682   // TODO: make this more efficient by backwards traversing.
1683   // For now, I know that we're generating graphs with tons of
1684   // unnecessary flag sets (which are immediately killed) and so
1685   // we don't have long non-exiting chains, we have "fuzz"
1686   
1687   NodeIterator nbegin, nend;
1688   ret->allNodes(nbegin, nend);
1689   
1690   std::list<Node::Ptr> toDelete;
1691   unsigned numNodes = 0;
1692   for (; nbegin != nend; ++nbegin) {
1693           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1694       numNodes++;
1695       SliceNode::Ptr foozle =
1696           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1697       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1698       if ((*nbegin)->hasOutEdges()) {
1699           slicing_cerr << "\t has out edges, leaving in" << endl;
1700           continue;
1701       }
1702
1703       // don't remove entry/exit nodes.
1704       if (ret->isEntryNode(*nbegin) || ret->isExitNode(*nbegin)) {
1705           continue;
1706       }
1707
1708       // mark non-flags nodes as exit nodes. these nodes are likely
1709       // relevant to the slice and should not be deleted. only delete 
1710       // flag nodes. this should stop the over-deleting by this
1711       // function, but this is a fairly ugly way of doing it. 
1712       const Absloc& abs = foozle->a_->out().absloc();
1713       if (abs.type() == Absloc::Register && 
1714                         (abs.reg().getArchitecture() == Arch_x86 
1715                          || abs.reg().getArchitecture() == Arch_x86_64) && 
1716                         (abs.reg().getBaseRegister() & x86::FLAG) == x86::FLAG) {
1717           slicing_cerr << "\t deleting" << endl;
1718           toDelete.push_back(*nbegin);
1719       } else {
1720           ret->markAsExitNode(foozle);
1721       }
1722   }
1723
1724   for (std::list<Node::Ptr>::iterator tmp =
1725            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1726       ret->deleteNode(*tmp);
1727   }
1728   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1729 }
1730
1731 // promotes nodes in the slice graph to termination nodes.
1732 // essentially, the slicer maintains a set of nodes that 
1733 // may be entry/exit nodes for the backwards/fowards case.
1734 // this function removes the nodes from the set, and 
1735 // marks them in the graph as true entry/exit nodes.
1736 // in the forward case, the entry node is a single node,
1737 // the assignment from which the slice began. in the backward
1738 // case, this node is the single exit node. exit nodes in the
1739 // forward case are definitions that are still live at function
1740 // exit. entry nodes in the backward case are uses for which the
1741 // definition lies outside the function (before entry) or move
1742 // instructions where one operand is a literal.
1743 void Slicer::promotePlausibleNodes(GraphPtr g, Direction d) {
1744     // note: it would be better to reuse some other
1745     // functions here, but none of them quite use 
1746     // the interface we need here.
1747     if (d == forward) {
1748         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1749              first != last; ++first) {
1750             g->markAsExitNode(*first);
1751         }
1752     } else {
1753         for (auto first = plausibleNodes.begin(), last = plausibleNodes.end();
1754              first != last; ++first) {
1755             g->markAsEntryNode(*first);
1756         }
1757     }
1758     plausibleNodes.clear();
1759 }
1760
1761 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1762                                    Direction dir) {
1763   return ((dir == forward) ? e->trg() : e->src());
1764 }
1765
1766 bool Slicer::isWidenNode(Node::Ptr n) {
1767   SliceNode::Ptr foozle =
1768     boost::dynamic_pointer_cast<SliceNode>(n);
1769   if (!foozle) return false;
1770   if (!foozle->assign()) return true;
1771   return false;
1772 }
1773
1774 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1775   if (dir == forward) {
1776     // Entry node
1777     ret->insertEntryNode(aP);
1778   }
1779   else {
1780     ret->insertExitNode(aP);
1781   }
1782 }
1783
1784 // creates the initial slice frame and initializes instance variables.
1785 void Slicer::constructInitialFrame(
1786     Direction dir,
1787     SliceFrame & initFrame)
1788 {
1789     Instruction::Ptr init_instruction;
1790     initFrame.con.push_front(ContextElement(f_));
1791     initFrame.loc = Location(f_,b_);
1792
1793     // increment iterators to initial instruction. 
1794     if(dir == forward) {
1795         initFrame.loc.fwd = true;
1796         getInsns(initFrame.loc);
1797         fastForward(initFrame.loc, a_->addr());
1798         init_instruction = initFrame.loc.current->first;
1799     } else {
1800         initFrame.loc.fwd = false;
1801         getInsnsBackward(initFrame.loc);
1802         fastBackward(initFrame.loc, a_->addr());
1803         init_instruction = initFrame.loc.rcurrent->first;
1804     }
1805
1806     // reconstruct initial assignment. the initial assignment was created
1807     // by a different converter, and thus if the instruction is visited
1808     // more than once by the slicer, the assignment will be recreated
1809     // instead of coming out of cache. this results in duplicated graph
1810     // nodes. 
1811     std::vector<Assignment::Ptr> assigns;
1812     convertInstruction(init_instruction, a_->addr(), f_, b_, assigns);
1813     for (auto first = assigns.begin(), last = assigns.end(); first != last; ++first) {
1814         if ((*first)->out() == a_->out()) { a_ = *first; break; }
1815     }
1816
1817     if(dir == forward) {
1818         Element oe(b_,f_,a_->out(),a_);
1819         initFrame.active[a_->out()].push_back(oe);
1820     } else {
1821         vector<AbsRegion> & inputs = a_->inputs();
1822         vector<AbsRegion>::iterator iit = inputs.begin();
1823         for ( ; iit != inputs.end(); ++iit) {
1824             Element ie(b_,f_,*iit,a_);
1825             initFrame.active[*iit].push_back(ie);
1826         }
1827     }
1828 }
1829
1830 void
1831 Slicer::DefCache::merge(Slicer::DefCache const& o)
1832 {
1833     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1834     for( ; oit != o.defmap.end(); ++oit) {
1835         AbsRegion const& r = oit->first;
1836         set<Def> const& s = oit->second;
1837         defmap[r].insert(s.begin(),s.end());
1838     }
1839 }
1840
1841 void
1842 Slicer::DefCache::replace(Slicer::DefCache const& o)
1843 {   
1844     // XXX if o.defmap[region] is empty set, remove that entry
1845     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1846     for( ; oit != o.defmap.end(); ++oit) {
1847         if(!(*oit).second.empty())
1848             defmap[(*oit).first] = (*oit).second;
1849         else
1850             defmap.erase((*oit).first);
1851     }
1852 }
1853
1854 void
1855 Slicer::DefCache::print() const {
1856     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1857     for( ; it !=defmap.end(); ++it) {
1858         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1859         set<Def> const& defs = (*it).second;
1860         set<Def>::const_iterator dit = defs.begin();
1861         for( ; dit != defs.end(); ++dit) {
1862             slicing_printf("\t\t\t<%s,%s>\n",
1863                 (*dit).ele.ptr->format().c_str(),
1864                 (*dit).data.format().c_str());
1865         }
1866     }
1867 }
1868
1869 // merges all single caches that have occured single addr in the
1870 // recursion into the appropriate unified caches.
1871 void Slicer::mergeRecursiveCaches(std::map<Address, DefCache>& single, 
1872                                   std::map<Address, DefCache>& unified, Address) {
1873
1874
1875     for (auto first = addrStack.rbegin(), last = addrStack.rend();
1876             first != last; ++first) {
1877         unified[*first].replace(single[*first]);
1878         auto next = first + 1;
1879         if (next != last) {
1880             unified[*next].merge(unified[*first]);
1881         }
1882     }
1883 }
1884