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