1. Fix sign extension
[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 bool
997 Slicer::handleDefault(
998     Direction dir,
999     Predicates & /*p*/,
1000     ParseAPI::Edge * e,
1001     SliceFrame & cur,
1002     bool & /* err */)
1003 {
1004     if(dir == forward) {
1005         cur.loc.block = e->trg();
1006         getInsns(cur.loc);
1007     } else {
1008         cur.loc.block = e->src();
1009         getInsnsBackward(cur.loc);
1010     }
1011     return true;
1012 }
1013
1014 /* ----------------- backwards slicing implementations ------------------ */
1015
1016 bool
1017 Slicer::handleCallBackward(
1018     Predicates & p,
1019     SliceFrame const& cand,
1020     vector<SliceFrame> & newCands,
1021     ParseAPI::Edge * e,
1022     bool & /* err */)
1023 {
1024     // We don't know which function the caller block belongs to,
1025     // so check each possibility against the predicate.
1026     //
1027     // XXX   this suffers the same problem as followCall in the forward
1028     //       case; the predicates test against only a single abstract
1029     //       region. What we do here is to build up mappings from
1030     //       function paths (that will be followed) to sets of abstract
1031     //       regions, then create SliceFrames with these sets.
1032
1033     map<ParseAPI::Function *, SliceFrame::ActiveMap > fmap;
1034
1035     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1036     for( ; ait != cand.active.end(); ++ait) {
1037         vector<ParseAPI::Function *> follow = 
1038             followCallBackward(p,cand,(*ait).first,e->src());
1039         for(unsigned j=0;j<follow.size();++j) {
1040             fmap[follow[j]].insert(*ait);
1041         }
1042     }
1043
1044     map<ParseAPI::Function *, SliceFrame::ActiveMap >::iterator mit = 
1045         fmap.begin();
1046     for( ; mit != fmap.end(); ++mit) {
1047         ParseAPI::Function * f = (*mit).first;
1048         SliceFrame::ActiveMap & act = (*mit).second;
1049     
1050         SliceFrame nf(cand.loc,cand.con);
1051         nf.active = act;
1052
1053         nf.con.push_back(ContextElement(f));
1054         nf.loc.block = e->src();
1055         nf.loc.func = f;
1056
1057         // pop context & adjust AbsRegions
1058         if(!handleCallDetailsBackward(nf)) {
1059             // FIXME I have preserved this behavior (returning false if
1060             //       the current frame can't be adjusted). It seems to
1061             //       me that we ought to set err = true and continue
1062             //       processing the rest of the call edges.
1063             //
1064             //       This issue needs review by somebody knowledgeable
1065             //       about the slicer.
1066             return false;
1067         }
1068
1069         getInsnsBackward(nf.loc);
1070         newCands.push_back(nf);
1071     } 
1072     return true;
1073 }
1074
1075 /*
1076  * FIXME egregious copying
1077  */
1078 vector<ParseAPI::Function *>
1079 Slicer::followCallBackward(
1080     Predicates & p,
1081     SliceFrame const& cand,
1082     AbsRegion const& reg,
1083     ParseAPI::Block * caller_block)
1084 {
1085     stack< pair<ParseAPI::Function *, int> > callStack;  
1086     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1087         calls != cand.con.rend(); ++calls)
1088     {
1089         if(calls->func) {
1090             callStack.push(
1091                std::make_pair(calls->func, calls->stackDepth));
1092         }
1093     }
1094     return p.followCallBackward(caller_block, callStack, reg);
1095 }
1096
1097 bool
1098 Slicer::handleCallDetailsBackward(
1099     SliceFrame & cur)
1100 {
1101     ParseAPI::Block * callBlock = cur.loc.block;
1102     ParseAPI::Function * caller = cur.loc.func;
1103
1104     Address callBlockLastInsn = callBlock->lastInsnAddr();
1105
1106     long stack_depth;
1107     if(!getStackDepth(caller, callBlock, callBlockLastInsn,stack_depth)) {
1108         return false;
1109     }
1110
1111     popContext(cur.con);
1112     assert(!cur.con.empty());
1113
1114
1115     slicing_printf("\t%s, %d\n",
1116         (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
1117         cur.con.front().stackDepth);
1118
1119     // Transform the active abstract regions
1120     shiftAllAbsRegions(cur,-1*stack_depth,caller);
1121
1122     return true;
1123 }
1124     
1125 bool
1126 Slicer::handleReturnBackward(
1127     Predicates & p,
1128     SliceFrame const& cand,
1129     SliceFrame & newCand,
1130     ParseAPI::Edge * e,
1131     bool & err)
1132 {
1133     ParseAPI::Block * callee = e->src();
1134
1135     // cons up a call stack for the call associated
1136     // with this return and ask the predicates whether
1137     // they would have come down this call.
1138     //
1139     // FIXME the issue of predicates evaluating only a
1140     //       single abstract region applies here as well;
1141     //       see comments in handleCall and handleCallBackward
1142
1143     if(followReturn(p,cand,callee)) {
1144         // XXX it is not clear to me why a null callee is an error here
1145         //     but not if followReturn returns false FIXME
1146         if(!callee) {
1147             err = true;
1148             return false;
1149         }
1150
1151         newCand = cand;
1152         newCand.loc.block = callee;
1153         newCand.loc.func = getEntryFunc(callee);
1154         getInsnsBackward(newCand.loc);
1155
1156         if(!handleReturnDetailsBackward(newCand,cand.loc.block)) {
1157             err = true;
1158             return false;
1159         }
1160         return true;
1161     }
1162
1163     return false;
1164 }
1165
1166 bool
1167 Slicer::handleReturnDetailsBackward(
1168     SliceFrame & cur,
1169     ParseAPI::Block * caller_block)
1170 {
1171     ParseAPI::Function * caller = cur.con.front().func;
1172     ParseAPI::Function * callee = cur.loc.func;
1173
1174     long stack_depth;
1175     if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
1176         return false;
1177     }
1178     
1179     pushContext(cur.con, callee, caller_block, stack_depth);
1180
1181     // Transform the active abstract regions
1182     shiftAllAbsRegions(cur,stack_depth,caller);
1183
1184     return true; 
1185 }
1186
1187 bool
1188 Slicer::followReturn(
1189     Predicates & p,
1190     SliceFrame const& cand,
1191     ParseAPI::Block * source)
1192 {
1193     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1194     
1195     stack< pair<ParseAPI::Function *, int> > callStack;
1196     for(Context::const_reverse_iterator calls = cand.con.rbegin();
1197         calls != cand.con.rend(); ++calls)
1198     {
1199         if(calls->func) {
1200             callStack.push(
1201                std::make_pair(calls->func, calls->stackDepth));
1202         }
1203     }
1204
1205     bool ret = false;
1206     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1207     for( ; ait != cand.active.end(); ++ait) {
1208         ret = ret || p.followCall(callee,callStack,(*ait).first);
1209     }
1210     return ret;
1211 }
1212     
1213
1214
1215 /* ------------------------------------------- */
1216
1217 Address SliceNode::addr() const { 
1218   if (a_)
1219     return a_->addr();
1220   return 0;
1221 }
1222
1223 bool containsCall(ParseAPI::Block *block) {
1224   // We contain a call if the out-edges include
1225   // either a CALL or a CALL_FT edge
1226   const Block::edgelist &targets = block->targets();
1227   Block::edgelist::const_iterator eit = targets.begin();
1228   for (; eit != targets.end(); ++eit) {
1229     ParseAPI::Edge *edge = *eit;
1230     if (edge->type() == CALL) return true;
1231   }
1232   return false;
1233 }
1234
1235 bool containsRet(ParseAPI::Block *block) {
1236   // We contain a call if the out-edges include
1237   // either a CALL or a CALL_FT edge
1238   const Block::edgelist &targets = block->targets();
1239   Block::edgelist::const_iterator eit = targets.begin();
1240   for (; eit != targets.end(); ++eit) {
1241     ParseAPI::Edge *edge = *eit;
1242     if (edge->type() == RET) return true;
1243   }
1244   return false;
1245 }
1246
1247 static void getInsnInstances(ParseAPI::Block *block,
1248                       Slicer::InsnVec &insns) {
1249   Offset off = block->start();
1250   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
1251   if (ptr == NULL) return;
1252   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
1253   while (off < block->end()) {
1254     insns.push_back(std::make_pair(d.decode(), off));
1255     off += insns.back().first->size();
1256   }
1257 }
1258
1259 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
1260   return block->obj()->findFuncByEntry(block->region(), block->start());
1261 }
1262
1263 // Constructor. Takes the initial point we slice from. 
1264
1265 // TODO: make this function-less interprocedural. That would throw the
1266 // stack analysis for a loop, but is generally doable...
1267 Slicer::Slicer(Assignment::Ptr a,
1268                ParseAPI::Block *block,
1269                ParseAPI::Function *func) : 
1270   a_(a),
1271   b_(block),
1272   f_(func),
1273   // Xiaozhu: Temporarily disable stackanalysis, should be able to
1274   // specify it 
1275   converter(true, false) {
1276   df_init_debug();
1277 };
1278
1279 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
1280
1281         // delete cache state
1282   unique_edges_.clear(); 
1283
1284   return sliceInternal(forward, predicates);
1285 }
1286
1287 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
1288   // delete cache state
1289   unique_edges_.clear(); 
1290
1291   return sliceInternal(backward, predicates);
1292 }
1293
1294 bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
1295   StackAnalysis sA(func);
1296
1297   StackAnalysis::Height heightSA = sA.findSP(block, callAddr);
1298
1299   // Ensure that analysis has been performed.
1300
1301   assert(!heightSA.isTop());
1302   
1303   if (heightSA.isBottom()) {
1304     return false;
1305   }
1306   
1307   height = heightSA.height();
1308   
1309   // The height will include the effects of the call
1310   // Should check the region... 
1311
1312   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
1313   //<< std::dec << " " << (int) height << endl;
1314
1315   return true;
1316 }
1317
1318 void Slicer::pushContext(Context &context,
1319                          ParseAPI::Function *callee,
1320                          ParseAPI::Block *callBlock,
1321                          long stackDepth) {
1322   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
1323   assert(context.front().block == NULL);
1324   context.front().block = callBlock;
1325
1326   slicing_cerr << "\t" 
1327                << (context.front().func ? context.front().func->name() : "NULL")
1328                << ", " 
1329                << context.front().stackDepth 
1330                << endl;
1331
1332     context.push_front(ContextElement(callee, stackDepth));
1333 };
1334
1335 void Slicer::popContext(Context &context) {
1336   context.pop_front();
1337
1338   context.front().block = NULL;
1339 }
1340
1341 void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
1342                             AbsRegion &calleeReg,
1343                             long stack_depth,
1344                             ParseAPI::Function *callee) {
1345   if (callerReg.absloc() == Absloc()) {
1346     // Typed, so just keep the same type and call it a day
1347     calleeReg = callerReg;
1348     return;
1349   }
1350   else {
1351     assert(callerReg.type() == Absloc::Unknown);
1352     
1353     const Absloc &callerAloc = callerReg.absloc();
1354     if (callerAloc.type() != Absloc::Stack) {
1355       calleeReg = AbsRegion(callerAloc);
1356     }
1357     else {
1358       if (stack_depth == -1) {
1359         // Oops
1360         calleeReg = AbsRegion(Absloc::Stack);
1361         return;
1362       }
1363       else {
1364         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
1365         //<< " by stack depth " << stack_depth 
1366         //<< " and setting to function " << callee->name() << endl;
1367         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
1368                                      0, // Entry point has region 0 by definition
1369                                      callee));
1370       }
1371     }
1372   }
1373 }
1374
1375 bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
1376   // Did we find a definition of the same abstract region?
1377   // TBD: overlaps ins't quite the right thing here. "contained
1378   // by" would be better, but we need to get the AND/OR
1379   // of abslocs hammered out.
1380
1381   if (assign->out().type() != Absloc::Unknown) {
1382     // A region assignment can never kill
1383     return false; 
1384   }
1385
1386   // Xiaozhu: A call can ruin all bounds, so we don't need to 
1387   // continue slicing. But need to figure out how to specify this
1388   // 2014-07-27: But actually sometimes we do need to slice across function calls
1389   // this is hard to decide.
1390   //if (assign->insn()->getCategory() == c_CallInsn) return true;
1391
1392   return reg.contains(assign->out());
1393 }
1394
1395 SliceNode::Ptr Slicer::createNode(Element const&elem) {
1396   if (created_.find(elem.ptr) != created_.end()) {
1397     return created_[elem.ptr];
1398   }
1399   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
1400   created_[elem.ptr] = newNode;
1401   return newNode;
1402 }
1403
1404 std::string SliceNode::format() const {
1405   if (!a_) {
1406     return "<NULL>";
1407   }
1408
1409   stringstream ret;
1410   ret << "(" << a_->format() << "@" <<
1411     f_->name() << ")";
1412   return ret.str();
1413 }
1414
1415 void Slicer::convertInstruction(Instruction::Ptr insn,
1416                                 Address addr,
1417                                 ParseAPI::Function *func,
1418                                 ParseAPI::Block *block,
1419                                 std::vector<Assignment::Ptr> &ret) {
1420   converter.convert(insn,
1421                     addr,
1422                     func,
1423                     block,
1424                     ret);
1425   return;
1426 }
1427
1428 void Slicer::getInsns(Location &loc) {
1429
1430
1431   InsnCache::iterator iter = insnCache_.find(loc.block);
1432   if (iter == insnCache_.end()) {
1433     getInsnInstances(loc.block, insnCache_[loc.block]);
1434   }
1435   
1436   loc.current = insnCache_[loc.block].begin();
1437   loc.end = insnCache_[loc.block].end();
1438 }
1439
1440 void Slicer::getInsnsBackward(Location &loc) {
1441     assert(loc.block->start() != (Address) -1); 
1442     InsnCache::iterator iter = insnCache_.find(loc.block);
1443     if (iter == insnCache_.end()) {
1444       getInsnInstances(loc.block, insnCache_[loc.block]);
1445     }
1446
1447     loc.rcurrent = insnCache_[loc.block].rbegin();
1448     loc.rend = insnCache_[loc.block].rend();
1449 }
1450
1451 void Slicer::insertPair(Graph::Ptr ret,
1452                         Direction dir,
1453                         Element const&source,
1454                         Element const&target,
1455                         AbsRegion const& data) 
1456 {
1457   SliceNode::Ptr s = createNode(source);
1458   SliceNode::Ptr t = createNode(target);
1459
1460   EdgeTuple et(s,t,data);
1461   if(unique_edges_.find(et) != unique_edges_.end()) {
1462     unique_edges_[et] += 1;
1463     return;
1464   }
1465   unique_edges_[et] = 1;  
1466
1467   if (dir == forward) {
1468      SliceEdge::Ptr e = SliceEdge::create(s, t, data);
1469      ret->insertPair(s, t, e);
1470   } else {
1471      SliceEdge::Ptr e = SliceEdge::create(t, s, data);
1472      ret->insertPair(t, s, e);
1473   }
1474 }
1475
1476 void
1477 Slicer::widenAll(
1478     Graph::Ptr g,
1479     Direction dir,
1480     SliceFrame const& cand)
1481 {
1482     SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
1483     for( ; ait != cand.active.end(); ++ait) {
1484         vector<Element> const& eles = (*ait).second;
1485         for(unsigned i=0;i<eles.size();++i)
1486             widen(g,dir,eles[i]);
1487     }
1488 }
1489
1490 void Slicer::widen(Graph::Ptr ret,
1491                    Direction dir,
1492                    Element const&e) {
1493   if (dir == forward) {
1494     ret->insertPair(createNode(e),
1495                     widenNode());
1496     ret->insertExitNode(widenNode());
1497   }
1498   else {
1499     ret->insertPair(widenNode(), createNode(e));
1500     ret->insertEntryNode(widenNode());
1501   }
1502 }
1503
1504 SliceNode::Ptr Slicer::widenNode() {
1505   if (widen_) {
1506     return widen_;
1507   }
1508
1509   widen_ = SliceNode::create(Assignment::Ptr(),
1510                               NULL, NULL);
1511   return widen_;
1512 }
1513
1514 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1515   if (dir == forward) {    
1516     ret->insertExitNode(createNode(e));
1517   }
1518   else {
1519     ret->insertEntryNode(createNode(e));
1520   }
1521 }
1522
1523 void Slicer::fastForward(Location &loc, Address
1524                          addr) {
1525   while ((loc.current != loc.end) &&
1526          (loc.addr() < addr)) {
1527     loc.current++;
1528   }
1529   assert(loc.current != loc.end);
1530   assert(loc.addr() == addr);
1531 }
1532
1533 void Slicer::fastBackward(Location &loc, Address addr) {
1534     while ((loc.rcurrent != loc.rend) &&
1535          (loc.addr() > addr)) {
1536     loc.rcurrent++;
1537   }
1538     
1539   assert(loc.rcurrent != loc.rend);
1540   assert(loc.addr() == addr);  
1541 }
1542
1543 void Slicer::cleanGraph(Graph::Ptr ret) {
1544   slicing_cerr << "Cleaning up the graph..." << endl;
1545   // Clean the graph up
1546   
1547   // TODO: make this more efficient by backwards traversing.
1548   // For now, I know that we're generating graphs with tons of
1549   // unnecessary flag sets (which are immediately killed) and so
1550   // we don't have long non-exiting chains, we have "fuzz"
1551   
1552   NodeIterator nbegin, nend;
1553   ret->allNodes(nbegin, nend);
1554   
1555   std::list<Node::Ptr> toDelete;
1556   unsigned numNodes = 0;
1557   for (; nbegin != nend; ++nbegin) {
1558           expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
1559       numNodes++;
1560       SliceNode::Ptr foozle =
1561           boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1562       //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1563       if ((*nbegin)->hasOutEdges()) {
1564           slicing_cerr << "\t has out edges, leaving in" << endl;
1565       
1566           // This cleans up case where we ended a backward slice
1567           // but never got to mark the node as an entry node
1568           if (!(*nbegin)->hasInEdges()) {
1569                   ret->markAsEntryNode(foozle);
1570           }
1571           continue;
1572       }
1573       if (ret->isExitNode(*nbegin)) {
1574           slicing_cerr << "\t is exit node, leaving in" << endl;
1575           // A very odd case - a graph of 1 node. Yay!
1576           if (!(*nbegin)->hasInEdges()) {
1577                   ret->markAsEntryNode(foozle);
1578           }
1579           continue;
1580       }
1581       slicing_cerr << "\t deleting" << endl;
1582       toDelete.push_back(*nbegin);
1583   }
1584
1585   for (std::list<Node::Ptr>::iterator tmp =
1586            toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1587       ret->deleteNode(*tmp);
1588   }
1589   slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
1590 }
1591
1592 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1593                                    Direction dir) {
1594   return ((dir == forward) ? e->trg() : e->src());
1595 }
1596
1597 bool Slicer::isWidenNode(Node::Ptr n) {
1598   SliceNode::Ptr foozle =
1599     boost::dynamic_pointer_cast<SliceNode>(n);
1600   if (!foozle) return false;
1601   if (!foozle->assign()) return true;
1602   return false;
1603 }
1604
1605 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1606   if (dir == forward) {
1607     // Entry node
1608     ret->insertEntryNode(aP);
1609   }
1610   else {
1611     ret->insertExitNode(aP);
1612   }
1613 }
1614  
1615 void Slicer::constructInitialFrame(
1616     Direction dir,
1617     SliceFrame & initFrame)
1618 {
1619     initFrame.con.push_front(ContextElement(f_));
1620     initFrame.loc = Location(f_,b_);
1621
1622     if(dir == forward) {
1623         Element oe(b_,f_,a_->out(),a_);
1624         initFrame.active[a_->out()].push_back(oe);
1625     } else {
1626         vector<AbsRegion> & inputs = a_->inputs();
1627         vector<AbsRegion>::iterator iit = inputs.begin();
1628         for ( ; iit != inputs.end(); ++iit) {
1629             Element ie(b_,f_,*iit,a_);
1630             initFrame.active[*iit].push_back(ie);
1631         }
1632     }
1633
1634     if(dir == forward) {
1635         initFrame.loc.fwd = true;
1636         getInsns(initFrame.loc);
1637         fastForward(initFrame.loc, a_->addr());
1638     } else {
1639         initFrame.loc.fwd = false;
1640         getInsnsBackward(initFrame.loc);
1641         fastBackward(initFrame.loc, a_->addr());
1642     }
1643 }
1644
1645 void
1646 Slicer::DefCache::merge(Slicer::DefCache const& o)
1647 {
1648     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1649     for( ; oit != o.defmap.end(); ++oit) {
1650         AbsRegion const& r = oit->first;
1651         set<Def> const& s = oit->second;
1652         defmap[r].insert(s.begin(),s.end());
1653     }
1654 }
1655
1656 void
1657 Slicer::DefCache::replace(Slicer::DefCache const& o)
1658 {   
1659     // XXX if o.defmap[region] is empty set, remove that entry
1660     map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
1661     for( ; oit != o.defmap.end(); ++oit) {
1662         if(!(*oit).second.empty())
1663             defmap[(*oit).first] = (*oit).second;
1664         else
1665             defmap.erase((*oit).first);
1666     }
1667 }
1668
1669 void
1670 Slicer::DefCache::print() const {
1671     map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
1672     for( ; it !=defmap.end(); ++it) {
1673         slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
1674         set<Def> const& defs = (*it).second;
1675         set<Def>::const_iterator dit = defs.begin();
1676         for( ; dit != defs.end(); ++dit) {
1677             slicing_printf("\t\t\t<%s,%s>\n",
1678                 (*dit).ele.ptr->format().c_str(),
1679                 (*dit).data.format().c_str());
1680         }
1681     }
1682 }