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