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