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