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