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