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