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