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