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