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