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