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