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