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