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