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