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