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