Fit code handling thunk into new analysis code
[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     } else { 
1182       // Xiaozhu: If the user decides to not follow into the callee,
1183       // we do not know for sure which register's values would stay
1184       // intact. All values of the reigsters can be changed by the callee.
1185       // We set err to true, and widen the slice
1186       err = true;
1187     }
1188
1189     return false;
1190 }
1191
1192 bool
1193 Slicer::handleReturnDetailsBackward(
1194     SliceFrame & cur,
1195     ParseAPI::Block * caller_block)
1196 {
1197     ParseAPI::Function * caller = cur.con.front().func;
1198     ParseAPI::Function * callee = cur.loc.func;
1199
1200     long stack_depth;
1201     if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
1202         return false;
1203     }
1204     
1205     pushContext(cur.con, callee, caller_block, stack_depth);
1206
1207     // Transform the active abstract regions
1208     shiftAllAbsRegions(cur,stack_depth,caller);
1209
1210     return true; 
1211 }
1212
1213 bool
1214 Slicer::followReturn(
1215     Predicates & p,
1216     SliceFrame const& cand,
1217     ParseAPI::Block * source)
1218 {
1219     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1220     
1221     stack< pair<ParseAPI::Function *, int> > callStack;
1222     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1223         calls != cand.con.rend(); ++calls)
1224     {
1225         if(calls->func) {
1226             callStack.push(
1227                std::make_pair(calls->func, calls->stackDepth));
1228         }
1229     }
1230
1231     bool ret = false;
1232     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1233     for( ; ait != cand.active.end(); ++ait) {
1234         ret = ret || p.followCall(callee,callStack,(*ait).first);
1235     }
1236     return ret;
1237 }
1238     
1239
1240
1241 /* ------------------------------------------- */
1242
1243 Address SliceNode::addr() const { 
1244   if (a_)
1245     return a_->addr();
1246   return 0;
1247 }
1248
1249 bool containsCall(ParseAPI::Block *block) {
1250   // We contain a call if the out-edges include
1251   // either a CALL or a CALL_FT edge
1252   const Block::edgelist &targets = block->targets();
1253   Block::edgelist::const_iterator eit = targets.begin();
1254   for (; eit != targets.end(); ++eit) {
1255     ParseAPI::Edge *edge = *eit;
1256     if (edge->type() == CALL) return true;
1257   }
1258   return false;
1259 }
1260
1261 bool containsRet(ParseAPI::Block *block) {
1262   // We contain a call if the out-edges include
1263   // either a CALL or a CALL_FT edge
1264   const Block::edgelist &targets = block->targets();
1265   Block::edgelist::const_iterator eit = targets.begin();
1266   for (; eit != targets.end(); ++eit) {
1267     ParseAPI::Edge *edge = *eit;
1268     if (edge->type() == RET) return true;
1269   }
1270   return false;
1271 }
1272
1273 static void getInsnInstances(ParseAPI::Block *block,
1274                       Slicer::InsnVec &insns) {
1275   Offset off = block->start();
1276   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
1277   if (ptr == NULL) return;
1278   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
1279   while (off < block->end()) {
1280     insns.push_back(std::make_pair(d.decode(), off));
1281     off += insns.back().first->size();
1282   }
1283 }
1284
1285 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
1286   return block->obj()->findFuncByEntry(block->region(), block->start());
1287 }
1288
1289 // Constructor. Takes the initial point we slice from. 
1290
1291 // TODO: make this function-less interprocedural. That would throw the
1292 // stack analysis for a loop, but is generally doable...
1293 Slicer::Slicer(Assignment::Ptr a,
1294                ParseAPI::Block *block,
1295                ParseAPI::Function *func) : 
1296   a_(a),
1297   b_(block),
1298   f_(func),
1299   // Xiaozhu: Temporarily disable stackanalysis, should be able to
1300   // specify it 
1301   converter(true, false) {
1302   df_init_debug();
1303 };
1304
1305 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
1306
1307         // delete cache state
1308   unique_edges_.clear(); 
1309
1310   return sliceInternal(forward, predicates);
1311 }
1312
1313 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
1314   // delete cache state
1315   unique_edges_.clear(); 
1316
1317   return sliceInternal(backward, predicates);
1318 }
1319
1320 bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
1321   StackAnalysis sA(func);
1322
1323   StackAnalysis::Height heightSA = sA.findSP(block, callAddr);
1324
1325   // Ensure that analysis has been performed.
1326
1327   assert(!heightSA.isTop());
1328   
1329   if (heightSA.isBottom()) {
1330     return false;
1331   }
1332   
1333   height = heightSA.height();
1334   
1335   // The height will include the effects of the call
1336   // Should check the region... 
1337
1338   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
1339   //<< std::dec << " " << (int) height << endl;
1340
1341   return true;
1342 }
1343
1344 void Slicer::pushContext(Context &context,
1345                          ParseAPI::Function *callee,
1346                          ParseAPI::Block *callBlock,
1347                          long stackDepth) {
1348   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
1349   assert(context.front().block == NULL);
1350   context.front().block = callBlock;
1351
1352   slicing_cerr << "\t" 
1353                << (context.front().func ? context.front().func->name() : "NULL")
1354                << ", " 
1355                << context.front().stackDepth 
1356                << endl;
1357
1358     context.push_front(ContextElement(callee, stackDepth));
1359 };
1360
1361 void Slicer::popContext(Context &context) {
1362   context.pop_front();
1363
1364   context.front().block = NULL;
1365 }
1366
1367 void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
1368                             AbsRegion &calleeReg,
1369                             long stack_depth,
1370                             ParseAPI::Function *callee) {
1371   if (callerReg.absloc() == Absloc()) {
1372     // Typed, so just keep the same type and call it a day
1373     calleeReg = callerReg;
1374     return;
1375   }
1376   else {
1377     assert(callerReg.type() == Absloc::Unknown);
1378     
1379     const Absloc &callerAloc = callerReg.absloc();
1380     if (callerAloc.type() != Absloc::Stack) {
1381       calleeReg = AbsRegion(callerAloc);
1382     }
1383     else {
1384       if (stack_depth == -1) {
1385         // Oops
1386         calleeReg = AbsRegion(Absloc::Stack);
1387         return;
1388       }
1389       else {
1390         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
1391         //<< " by stack depth " << stack_depth 
1392         //<< " and setting to function " << callee->name() << endl;
1393         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
1394                                      0, // Entry point has region 0 by definition
1395                                      callee));
1396       }
1397     }
1398   }
1399 }
1400
1401 bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
1402   // Did we find a definition of the same abstract region?
1403   // TBD: overlaps ins't quite the right thing here. "contained
1404   // by" would be better, but we need to get the AND/OR
1405   // of abslocs hammered out.
1406   
1407   if (assign->out().type() != Absloc::Unknown) {
1408     // A region assignment can never kill
1409     return false; 
1410   }
1411
1412   return reg.contains(assign->out());
1413 }
1414
1415 SliceNode::Ptr Slicer::createNode(Element const&elem) {
1416   if (created_.find(elem.ptr) != created_.end()) {
1417     return created_[elem.ptr];
1418   }
1419   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
1420   created_[elem.ptr] = newNode;
1421   return newNode;
1422 }
1423
1424 std::string SliceNode::format() const {
1425   if (!a_) {
1426     return "<NULL>";
1427   }
1428
1429   stringstream ret;
1430   ret << "(" << a_->format() << "@" <<
1431     f_->name() << ")";
1432   return ret.str();
1433 }
1434
1435 void Slicer::convertInstruction(Instruction::Ptr insn,
1436                                 Address addr,
1437                                 ParseAPI::Function *func,
1438                                 ParseAPI::Block *block,
1439                                 std::vector<Assignment::Ptr> &ret) {
1440   converter.convert(insn,
1441                     addr,
1442                     func,
1443                     block,
1444                     ret);
1445   return;
1446 }
1447
1448 void Slicer::getInsns(Location &loc) {
1449
1450
1451   InsnCache::iterator iter = insnCache_.find(loc.block);
1452   if (iter == insnCache_.end()) {
1453     getInsnInstances(loc.block, insnCache_[loc.block]);
1454   }
1455   
1456   loc.current = insnCache_[loc.block].begin();
1457   loc.end = insnCache_[loc.block].end();
1458 }
1459
1460 void Slicer::getInsnsBackward(Location &loc) {
1461     assert(loc.block->start() != (Address) -1); 
1462     InsnCache::iterator iter = insnCache_.find(loc.block);
1463     if (iter == insnCache_.end()) {
1464       getInsnInstances(loc.block, insnCache_[loc.block]);
1465     }
1466
1467     loc.rcurrent = insnCache_[loc.block].rbegin();
1468     loc.rend = insnCache_[loc.block].rend();
1469 }
1470
1471 void Slicer::insertPair(Graph::Ptr ret,
1472                         Direction dir,
1473                         Element const&source,
1474                         Element const&target,
1475                         AbsRegion const& data) 
1476 {
1477   SliceNode::Ptr s = createNode(source);
1478   SliceNode::Ptr t = createNode(target);
1479
1480   EdgeTuple et(s,t,data);
1481   if(unique_edges_.find(et) != unique_edges_.end()) {
1482     unique_edges_[et] += 1;
1483     return;
1484   }
1485   unique_edges_[et] = 1;  
1486
1487   if (dir == forward) {
1488      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1489      ret->insertPair(s, t, e);
1490   } else {
1491      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1492      ret->insertPair(t, s, e);
1493   }
1494 }
1495
1496 void
1497 Slicer::widenAll(
1498     Graph::Ptr g,
1499     Direction dir,
1500     SliceFrame const& cand)
1501 {
1502     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1503     for( ; ait != cand.active.end(); ++ait) {
1504         vector<Element> const& eles = (*ait).second;
1505         for(unsigned i=0;i<eles.size();++i)
1506             widen(g,dir,eles[i]);
1507     }
1508 }
1509
1510 void Slicer::widen(Graph::Ptr ret,
1511                    Direction dir,
1512                    Element const&e) {
1513   if (dir == forward) {
1514     ret->insertPair(createNode(e),
1515                     widenNode());
1516     ret->insertExitNode(widenNode());
1517   }
1518   else {
1519     ret->insertPair(widenNode(), createNode(e));
1520     ret->insertEntryNode(widenNode());
1521   }
1522 }
1523
1524 SliceNode::Ptr Slicer::widenNode() {
1525   if (widen_) {
1526     return widen_;
1527   }
1528
1529   widen_ = SliceNode::create(Assignment::Ptr(),
1530                               NULL, NULL);
1531   return widen_;
1532 }
1533
1534 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1535   if (dir == forward) {    
1536     ret->insertExitNode(createNode(e));
1537   }
1538   else {
1539     ret->insertEntryNode(createNode(e));
1540   }
1541 }
1542
1543 void Slicer::fastForward(Location &loc, Address
1544                          addr) {
1545   while ((loc.current != loc.end) &&
1546          (loc.addr() < addr)) {
1547     loc.current++;
1548   }
1549   assert(loc.current != loc.end);
1550   assert(loc.addr() == addr);
1551 }
1552
1553 void Slicer::fastBackward(Location &loc, Address addr) {
1554     while ((loc.rcurrent != loc.rend) &&
1555          (loc.addr() > addr)) {
1556     loc.rcurrent++;
1557   }
1558     
1559   assert(loc.rcurrent != loc.rend);
1560   assert(loc.addr() == addr);  
1561 }
1562
1563 void Slicer::cleanGraph(Graph::Ptr ret) {
1564   slicing_cerr << "Cleaning up the graph..." << endl;
1565   // Clean the graph up
1566   
1567   // TODO: make this more efficient by backwards traversing.
1568   // For now, I know that we're generating graphs with tons of
1569   // unnecessary flag sets (which are immediately killed) and so
1570   // we don't have long non-exiting chains, we have "fuzz"
1571   
1572   NodeIterator nbegin, nend;
1573   ret->allNodes(nbegin, nend);
1574   
1575   std::list<Node::Ptr> toDelete;
1576   unsigned numNodes = 0;
1577   for (; nbegin != nend; ++nbegin) {
1578           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1579       numNodes++;
1580       SliceNode::Ptr foozle =
1581           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1582       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1583       if ((*nbegin)->hasOutEdges()) {
1584           slicing_cerr << "\t has out edges, leaving in" << endl;
1585       
1586           // This cleans up case where we ended a backward slice
1587           // but never got to mark the node as an entry node
1588           if (!(*nbegin)->hasInEdges()) {
1589                   ret->markAsEntryNode(foozle);
1590           }
1591           continue;
1592       }
1593       if (ret->isExitNode(*nbegin)) {
1594           slicing_cerr << "\t is exit node, leaving in" << endl;
1595           // A very odd case - a graph of 1 node. Yay!
1596           if (!(*nbegin)->hasInEdges()) {
1597                   ret->markAsEntryNode(foozle);
1598           }
1599           continue;
1600       }
1601       slicing_cerr << "\t deleting" << endl;
1602       toDelete.push_back(*nbegin);
1603   }
1604
1605   for (std::list<Node::Ptr>::iterator tmp =
1606            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1607       ret->deleteNode(*tmp);
1608   }
1609   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1610 }
1611
1612 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1613                                    Direction dir) {
1614   return ((dir == forward) ? e->trg() : e->src());
1615 }
1616
1617 bool Slicer::isWidenNode(Node::Ptr n) {
1618   SliceNode::Ptr foozle =
1619     boost::dynamic_pointer_cast<SliceNode>(n);
1620   if (!foozle) return false;
1621   if (!foozle->assign()) return true;
1622   return false;
1623 }
1624
1625 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1626   if (dir == forward) {
1627     // Entry node
1628     ret->insertEntryNode(aP);
1629   }
1630   else {
1631     ret->insertExitNode(aP);
1632   }
1633 }
1634  
1635 void Slicer::constructInitialFrame(
1636     Direction dir,
1637     SliceFrame & initFrame)
1638 {
1639     initFrame.con.push_front(ContextElement(f_));
1640     initFrame.loc = Location(f_,b_);
1641
1642     if(dir == forward) {
1643         Element oe(b_,f_,a_->out(),a_);
1644         initFrame.active[a_->out()].push_back(oe);
1645     } else {
1646         vector<AbsRegion> & inputs = a_->inputs();
1647         vector<AbsRegion>::iterator iit = inputs.begin();
1648         for ( ; iit != inputs.end(); ++iit) {
1649             Element ie(b_,f_,*iit,a_);
1650             initFrame.active[*iit].push_back(ie);
1651         }
1652     }
1653
1654     if(dir == forward) {
1655         initFrame.loc.fwd = true;
1656         getInsns(initFrame.loc);
1657         fastForward(initFrame.loc, a_->addr());
1658     } else {
1659         initFrame.loc.fwd = false;
1660         getInsnsBackward(initFrame.loc);
1661         fastBackward(initFrame.loc, a_->addr());
1662     }
1663 }
1664
1665 void
1666 Slicer::DefCache::merge(Slicer::DefCache const& o)
1667 {
1668     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1669     for( ; oit != o.defmap.end(); ++oit) {
1670         AbsRegion const& r = oit->first;
1671         set<Def> const& s = oit->second;
1672         defmap[r].insert(s.begin(),s.end());
1673     }
1674 }
1675
1676 void
1677 Slicer::DefCache::replace(Slicer::DefCache const& o)
1678 {   
1679     // XXX if o.defmap[region] is empty set, remove that entry
1680     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1681     for( ; oit != o.defmap.end(); ++oit) {
1682         if(!(*oit).second.empty())
1683             defmap[(*oit).first] = (*oit).second;
1684         else
1685             defmap.erase((*oit).first);
1686     }
1687 }
1688
1689 void
1690 Slicer::DefCache::print() const {
1691     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1692     for( ; it !=defmap.end(); ++it) {
1693         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1694         set<Def> const& defs = (*it).second;
1695         set<Def>::const_iterator dit = defs.begin();
1696         for( ; dit != defs.end(); ++dit) {
1697             slicing_printf("\t\t\t<%s,%s>\n",
1698                 (*dit).ele.ptr->format().c_str(),
1699                 (*dit).data.format().c_str());
1700         }
1701     }
1702 }