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