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