Fix memory leak in memory emulation; add a predicate to widen slices before we chase...
[dyninst.git] / dataflowAPI / src / slicing.C
1 // Simple search mechanism to assist in short-range slicing.
2
3 #include <set>
4 #include <vector>
5 #include <queue>
6 #include "dataflowAPI/h/Absloc.h"
7 #include "dataflowAPI/h/AbslocInterface.h"
8 #include "Instruction.h"
9
10 #include "dataflowAPI/h/stackanalysis.h"
11
12 #include "dataflowAPI/h/slicing.h"
13
14 #include "dynutil/h/Graph.h"
15 #include "instructionAPI/h/Instruction.h"
16 #include "instructionAPI/h/InstructionDecoder.h"
17
18 #include "debug_dataflow.h"
19
20 #include "parseAPI/h/CFG.h"
21 #include "parseAPI/h/CodeSource.h"
22 #include "parseAPI/h/CodeObject.h"
23
24 using namespace Dyninst;
25 using namespace InstructionAPI;
26 using namespace std;
27 using namespace ParseAPI;
28
29 Address SliceNode::addr() const { 
30   if (a_)
31     return a_->addr();
32   return 0;
33 }
34
35 bool containsCall(ParseAPI::Block *block) {
36   // We contain a call if the out-edges include
37   // either a CALL or a CALL_FT edge
38   const Block::edgelist &targets = block->targets();
39   Block::edgelist::iterator eit = targets.begin();
40   for (; eit != targets.end(); ++eit) {
41     ParseAPI::Edge *edge = *eit;
42     if (edge->type() == CALL) return true;
43   }
44   return false;
45 }
46
47 bool containsRet(ParseAPI::Block *block) {
48   // We contain a call if the out-edges include
49   // either a CALL or a CALL_FT edge
50   const Block::edgelist &targets = block->targets();
51   Block::edgelist::iterator eit = targets.begin();
52   for (; eit != targets.end(); ++eit) {
53     ParseAPI::Edge *edge = *eit;
54     if (edge->type() == RET) return true;
55   }
56   return false;
57 }
58
59 static void getInsnInstances(ParseAPI::Block *block,
60                       Slicer::InsnVec &insns) {
61   Offset off = block->start();
62   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
63   if (ptr == NULL) return;
64   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
65   while (off < block->end()) {
66     insns.push_back(std::make_pair(d.decode(), off));
67     off += insns.back().first->size();
68   }
69 }
70
71 ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
72   return block->obj()->findFuncByEntry(block->region(), block->start());
73 }
74
75 // Constructor. Takes the initial point we slice from. 
76
77 // TODO: make this function-less interprocedural. That would throw the
78 // stack analysis for a loop, but is generally doable...
79 Slicer::Slicer(Assignment::Ptr a,
80                ParseAPI::Block *block,
81                ParseAPI::Function *func) : 
82   a_(a),
83   b_(block),
84   f_(func),
85   converter(true) {
86   df_init_debug();
87 };
88
89 Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {
90    cerr << "Forward slice..." << endl;
91   return sliceInternal(forward, predicates);
92 }
93
94 Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
95   return sliceInternal(backward, predicates);
96 }
97
98 Graph::Ptr Slicer::sliceInternal(Direction dir,
99                                  Predicates &p) {
100   Graph::Ptr ret = Graph::createGraph();
101
102   // This does the work of forward or backwards slicing;
103   // the few different operations are flagged by the
104   // direction.
105
106   // e tells us when we should end (naturally)
107   // w tells us when we should end and widen
108   // c determines whether a call should be followed or skipped
109   // a does ???
110   
111   Element initial;
112   constructInitialElement(initial, dir);
113   //     constructInitialElementBackward(initial);
114
115   SliceNode::Ptr aP = createNode(initial);
116   if (dir == forward) {
117       slicing_cerr << "Inserting entry node " << aP << "/" << aP->format() << endl;
118   } else {
119       slicing_cerr << "Inserting exit node " << aP << "/" << aP->format() << endl;
120     }
121
122   insertInitialNode(ret, dir, aP);
123
124   Elements worklist;
125   worklist.push(initial);
126
127   std::set<Assignment::Ptr> visited;
128
129   while (!worklist.empty()) {
130     Element current = worklist.front(); worklist.pop();
131
132     assert(current.ptr);
133
134     // As a note, anything we see here has already been added to the
135     // return graph. We're trying to decide whether to keep searching.
136
137     // Don't get stuck in a loop
138     if (visited.find(current.ptr) != visited.end()) {
139       slicing_cerr << "\t Already visited, skipping" << endl;
140       continue;
141     }
142     else {
143       visited.insert(current.ptr);
144     }
145
146     slicing_cerr << "\tSlicing from " << current.ptr->format() << endl;
147     
148     // Do we widen out? This should check the defined
149     // abstract region...
150     if (p.widenAtPoint(current.ptr)) {
151       slicing_cerr << "\t\t... widens slice" << endl;
152       widen(ret, dir, current);
153       continue;
154     }
155
156     // Do we stop here according to the end predicate?
157     if (p.endAtPoint(current.ptr)) {
158       slicing_cerr << "\t\t... ends slice" << endl;
159       markAsEndNode(ret, dir, current);
160       continue;
161     }
162
163     Elements found;
164     
165     if (!getMatchingElements(current, found, p, dir)) {
166       widen(ret, dir, current);
167     }
168     // We actually want to fall through; it's possible to have
169     // a partially successful search.
170
171     while (!found.empty()) {
172       Element target = found.front(); found.pop();
173       if (target.valid) {
174          insertPair(ret, dir, current, target);
175          worklist.push(target);
176       }
177       else {
178          widen(ret, dir, current);
179       }
180     }
181   }
182
183   cleanGraph(ret);
184   slicing_cerr << "... done" << endl;
185   return ret;
186 }
187   
188 bool Slicer::getMatchingElements(Element &current,
189                                  Elements &found,
190                                  Predicates &p,
191                                  Direction dir) {
192   bool ret = true;
193   if (dir == forward) {
194     // Find everyone who uses what this ptr defines
195     current.reg = current.ptr->out();
196     
197     if (!search(current, found, p, 
198                 // it's set when we find a match
199                 forward)) {
200       ret = false;
201     }
202   }
203   else {
204     assert(dir == backward);
205
206     // Find everyone who defines what this instruction uses
207     std::vector<AbsRegion> inputs = current.ptr->inputs();
208
209     for (unsigned int k = 0; k < inputs.size(); ++k) {
210       // Do processing on each input
211       current.reg = inputs[k];
212
213       if (!search(current, found, p, backward)) {
214         slicing_cerr << "\t\t... backward search failed" << endl;
215         ret = false;
216       }
217     }
218   }
219   return ret;
220 }
221
222 bool Slicer::getStackDepth(ParseAPI::Function *func, Address callAddr, long &height) {
223   StackAnalysis sA(func);
224
225   StackAnalysis::Height heightSA = sA.findSP(callAddr);
226
227   // Ensure that analysis has been performed.
228
229   assert(!heightSA.isTop());
230   
231   if (heightSA.isBottom()) {
232     return false;
233   }
234   
235   height = heightSA.height();
236
237   //slicing_cerr << "Get stack depth at " << std::hex << callAddr
238   //<< std::dec << " " << (int) height << endl;
239
240   return true;
241 }
242
243 void Slicer::pushContext(Context &context,
244                          ParseAPI::Function *callee,
245                          ParseAPI::Block *callBlock,
246                          long stackDepth) {
247   slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
248   assert(context.front().block == NULL);
249   context.front().block = callBlock;
250
251   //cerr << "Saving block @ " << hex << callBlock->end() << dec << " as call block" << endl;
252
253   slicing_cerr << "\t" 
254                << (context.front().func ? context.front().func->name() : "NULL")
255                << ", " 
256                << context.front().stackDepth 
257                << endl;
258
259     context.push_front(ContextElement(callee, stackDepth));
260 };
261
262 void Slicer::popContext(Context &context) {
263   context.pop_front();
264
265   context.front().block = NULL;
266 }
267
268 void Slicer::shiftAbsRegion(AbsRegion &callerReg,
269                             AbsRegion &calleeReg,
270                             long stack_depth,
271                             ParseAPI::Function *callee) {
272   if (callerReg.absloc() == Absloc()) {
273     // Typed, so just keep the same type and call it a day
274     calleeReg = callerReg;
275     return;
276   }
277   else {
278     assert(callerReg.type() == Absloc::Unknown);
279     
280     const Absloc &callerAloc = callerReg.absloc();
281     if (callerAloc.type() != Absloc::Stack) {
282       calleeReg = AbsRegion(callerAloc);
283     }
284     else {
285       if (stack_depth == -1) {
286         // Oops
287         calleeReg = AbsRegion(Absloc::Stack);
288         return;
289       }
290       else {
291         //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
292         //<< " by stack depth " << stack_depth 
293         //<< " and setting to function " << callee->name() << endl;
294         calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
295                                      0, // Entry point has region 0 by definition
296                                      callee));
297       }
298     }
299   }
300 }
301
302 bool Slicer::handleCallDetails(AbsRegion &reg,
303                         Context &context,
304                         ParseAPI::Block *callerBlock,
305                         ParseAPI::Function *callee) {
306   ParseAPI::Function *caller = context.front().func;
307   AbsRegion newReg = reg;
308
309   long stack_depth;
310   if (!getStackDepth(caller, callerBlock->lastInsnAddr(), stack_depth)) {
311     return false;
312   }
313
314   // By definition, the stack of the callee starts _before_ the call instruction,
315   // so we take the pre-call stack height and run with it. 
316
317   // Increment the context
318   pushContext(context, callee, callerBlock, stack_depth);
319
320   // Translate the AbsRegion from caller to callee
321   shiftAbsRegion(reg,
322                  newReg,
323                  stack_depth,
324                  callee);
325
326   //slicing_cerr << "After call, context has " << context.size() << " elements" << endl;
327   //slicing_cerr << "\t" << (context.front().func ? context.front().func->name() : "NULL")
328   //       << ", " << context.front().stackDepth << endl;
329
330   reg = newReg;
331   return true;
332 }
333
334 void Slicer::handleReturnDetails(AbsRegion &reg,
335                                  Context &context) {
336   // We need to add back the appropriate stack depth, basically
337   // reversing what we did in handleCall
338
339   //  slicing_cerr << "Return: context has " << context.size() << " elements" << endl;
340   //slicing_cerr << "\t" << (context.front().func ? context.front().func->name() : "NULL")
341   //<< ", " << context.front().stackDepth << endl;
342
343   long stack_depth = context.front().stackDepth;
344
345   popContext(context);
346
347   assert(!context.empty());
348
349   slicing_cerr << "\t" << (context.front().func ?
350                            context.front().func->name() : "NULL")
351                << ", " << context.front().stackDepth << endl;
352
353
354   AbsRegion newRegion;
355   shiftAbsRegion(reg, newRegion,
356                  -1*stack_depth,
357                  context.front().func);
358   reg = newRegion;
359 }
360
361 bool Slicer::handleReturnDetailsBackward(AbsRegion &reg,
362         Context &context,
363         ParseAPI::Block *callerBlock,
364         ParseAPI::Function *callee)
365 {
366     ParseAPI::Function * caller = context.front().func;
367     AbsRegion newReg = reg;
368
369     long stack_depth;
370     if (!getStackDepth(caller, callerBlock->end(), stack_depth)) {
371         return false;
372     }
373
374     // Increment the context
375     pushContext(context, callee, callerBlock, stack_depth);
376
377     // Translate the AbsRegion from caller to callee
378     shiftAbsRegion(reg,
379             newReg,
380             stack_depth,
381             callee);
382
383     reg = newReg;
384     return true;
385 }
386
387 bool Slicer::handleCallDetailsBackward(AbsRegion &reg,
388                                         Context &context,
389                                         ParseAPI::Block * callBlock,
390                                         ParseAPI::Function *caller) {
391
392     Address callBlockLastInsn = callBlock->lastInsnAddr();
393
394     long stack_depth;
395     if (!getStackDepth(caller, callBlockLastInsn, stack_depth)) {
396         return false;
397     }
398     
399     popContext(context);
400
401     assert(!context.empty());
402
403     slicing_cerr << "\t" << (context.front().func ?
404             context.front().func->name() : "NULL")
405         << ", " << context.front().stackDepth << endl;
406
407     AbsRegion newRegion;
408     shiftAbsRegion(reg, newRegion,
409             -1*stack_depth,
410             caller);
411
412     reg = newRegion;
413     
414     return true;
415 }
416
417 // Given a <location> this function returns a list of successors.
418 // If the successor is in a different function the searched-for
419 // AbsRegion should be updated (along with the context) but this
420 // doesn't handle that. 
421
422 bool Slicer::getSuccessors(Element &current,
423                            Elements &succ,
424                            Predicates &p) {
425   // Simple case: if we're not at the end of the instructions
426   // in this block, then add the next one and return.
427
428   InsnVec::iterator next = current.loc.current;
429   next++;
430
431   if (next != current.loc.end) {
432     Element newElement = current;
433     // We're in the same context since we're in the same block
434     // Also, AbsRegion
435     // But update the Location
436     newElement.loc.current = next;
437     succ.push(newElement);
438
439     slicing_cerr << "\t\t\t\t Adding intra-block successor " << newElement.reg.format() << endl;
440
441     return true;
442   }
443
444   bool ret = true;
445   // At the end of the block: set up the next blocks.
446   bool err = false;
447
448   if (containsCall(current.loc.block)) {
449     Element newElement;
450     slicing_cerr << "\t\t Handling call:";
451     if (handleCall(current.loc.block,
452                    current,
453                    newElement,
454                    p, 
455                    err)) {
456       slicing_cerr << " succeeded, err " << err << endl;
457       succ.push(newElement);
458     }
459   }
460   else if (containsRet(current.loc.block)) {
461     Element newElement;
462     slicing_cerr << "\t\t Handling return:";
463     if (handleReturn(current.loc.block,
464                      current,
465                      newElement,
466                      p,
467                      err)) {
468       slicing_cerr << " succeeded, err " << err << endl;
469       succ.push(newElement);
470     }
471   }
472   else {
473     const Block::edgelist &targets = current.loc.block->targets();
474     Block::edgelist::iterator eit = targets.begin();
475     for (; eit != targets.end(); ++eit) {
476       Element newElement;
477       if ((*eit)->sinkEdge()) {
478          newElement.valid = false;
479          succ.push(newElement);
480       }
481       else if (handleDefault(*eit,
482                              forward,
483                              current,
484                              newElement,
485                              p,
486                              err)) {
487          succ.push(newElement);
488       }
489       else {
490          cerr << " failed handleDefault, err " << err << endl;
491       }
492     }
493   }
494   if (err) {
495     ret = false;
496   }
497   
498   return ret;
499 }
500
501 bool Slicer::getPredecessors(Element &current, 
502                              Elements &pred,
503                              Predicates &p) 
504 {
505     // Simple case: if we're not at the beginning of the instructions
506     // in the block, then add the previous one and return
507     InsnVec::reverse_iterator prev = current.loc.rcurrent;
508     prev++;
509
510     if (prev != current.loc.rend) {
511         Element newElement = current;
512         // We're in the same context since we're in the same block
513         // Also, AbsRegion
514         // But update the Location
515         newElement.loc.rcurrent = prev;
516
517         if (p.addPredecessor(newElement.reg)) {
518             pred.push(newElement);
519
520             slicing_cerr << "\t\t\t\t Adding intra-block predecessor " 
521                 << std::hex << newElement.loc.addr() << " "  
522                 << newElement.reg.format() << endl;
523             slicing_cerr << "\t\t\t\t Current region is " << current.reg.format() 
524                 << endl;
525         }
526         return true;
527     }
528     
529     bool ret = true;
530     bool err = false;
531
532     Element newElement;
533     Elements newElements;
534     //SingleContext epredSC(current.loc.func, true, true);
535     //Interproc epred;
536     SingleContextOrInterproc epred(current.loc.func, true, true);
537
538     const Block::edgelist &sources = current.loc.block->sources();
539     Block::edgelist::iterator eit = sources.begin(&epred);
540     for ( ; eit != sources.end(); ++eit) {   
541       switch ((*eit)->type()) {
542       case CALL:
543         slicing_cerr << "\t\t Handling call:";
544         if (handleCallBackward(*eit,
545                     current,
546                     newElements,
547                     p,
548                     err)) {
549             slicing_cerr << " succeeded, err " <<err << endl;
550             while (newElements.size()) {
551                 newElement = newElements.front(); newElements.pop();
552                 pred.push(newElement);
553             }
554         }
555         break;
556       case RET:
557         slicing_cerr << "\t\t Handling return:";
558         if (handleReturnBackward(*eit,
559                     current,
560                     newElement,
561                     p,
562                     err)) {
563             slicing_cerr << " succeeded, err " << err << endl;
564             pred.push(newElement);
565         }
566         break;
567       default:
568             Element newElement;
569         if (handleDefault((*eit),
570                           backward,
571                           current,
572                           newElement,
573                           p,
574                           err)) {
575             pred.push(newElement);
576         }    
577       }
578     }
579     if (err) {
580       ret = false;
581     }
582     return ret;
583  
584 }
585
586
587 bool Slicer::handleDefault(ParseAPI::Edge *e,
588         Direction dir,
589         Element &current,
590         Element &newElement,
591         Predicates &,
592         bool &) {
593     // Since we're in the same function we can keep the AbsRegion
594     // and Context. Instead we only need to update the Location
595     newElement = current;
596
597     if (dir == forward) {
598         newElement.loc.block = e->trg();
599
600         // Cache the new vector of instruction instances and get iterators into it
601         getInsns(newElement.loc);
602     } else {
603         newElement.loc.block = e->src();
604
605         getInsnsBackward(newElement.loc);
606     }
607
608     return true;
609
610 }
611
612 bool Slicer::handleCall(ParseAPI::Block *block,
613                         Element &current,
614                         Element &newElement,
615                         Predicates &p,
616                         bool &err) {
617   ParseAPI::Block *callee = NULL;
618   ParseAPI::Edge *funlink = NULL;
619
620   const Block::edgelist &targets = block->targets();
621   Block::edgelist::iterator eit = targets.begin();
622   for (; eit != targets.end(); ++eit) {
623     if ((*eit)->sinkEdge()) {
624       err = true; 
625       continue;
626     }
627     if ((*eit)->type() == CALL) {
628       callee = (*eit)->trg();
629     }
630     else if ((*eit)->type() == CALL_FT) {
631       funlink = (*eit);
632     }
633   }
634
635   if (followCall(callee, forward, current, p)) {
636     if (!callee) {
637       err = true;
638       return false;
639     }
640
641     newElement = current;
642     // Update location
643     newElement.loc.block = callee;
644     newElement.loc.func = getEntryFunc(callee);
645     assert(newElement.loc.func);
646     getInsns(newElement.loc);
647     
648     // HandleCall updates both an AbsRegion and a context...
649     if (!handleCallDetails(newElement.reg,
650                            newElement.con,
651                            current.loc.block,
652                            newElement.loc.func)) {
653       slicing_cerr << "Handle of call details failed!" << endl;
654       err = true;
655       return false;
656     }
657   }
658   else {
659     // Use the funlink
660     if (!funlink) {
661       // ???
662       return false;
663     }
664     if (!handleDefault(funlink,
665                        forward,
666                        current,
667                        newElement,
668                        p,
669                        err)) {
670       slicing_cerr << "handleDefault failed!" << endl;
671       err = true;
672       return false;
673     }
674   }
675   
676   return true;
677 }
678
679 bool Slicer::handleCallBackward(ParseAPI::Edge *edge,
680         Element &current,
681         Elements &newElements,
682         Predicates &p,
683         bool &)
684 {
685     Element newElement = current;
686
687     newElement.loc.block = edge->src();
688
689     /* We don't know which function the caller block belongs to,
690      * follow each possibility */
691     std::vector<ParseAPI::Function *> funcsToFollow = followCallBackward(newElement.loc.block, backward, current, p);
692
693     std::vector<ParseAPI::Function *>::iterator fit;
694     for (fit = funcsToFollow.begin(); fit != funcsToFollow.end(); ++fit) {
695         Element curElement = newElement;
696         curElement.con.push_back(ContextElement(*fit));
697
698         // Pop AbsRegion and Context
699         if (!handleCallDetailsBackward(curElement.reg,
700                     curElement.con,
701                     curElement.loc.block,
702                     *fit)) {
703             return false;
704         }
705
706         curElement.loc.func = *fit;
707         getInsnsBackward(curElement.loc);
708         newElements.push(curElement);
709     }
710
711     return true;
712 }
713
714 bool Slicer::handleReturn(ParseAPI::Block *,
715                           Element &current,
716                           Element &newElement,
717                           Predicates &,
718                           bool &err) {
719   // As handleCallEdge, but now with 50% fewer calls
720   newElement = current;
721
722   // Find out the successor block...
723   Context callerCon = newElement.con;
724   callerCon.pop_front();
725
726   if (callerCon.empty()) {
727     return false;
728   }
729
730   ParseAPI::Block *retBlock = NULL;
731
732 #if 0
733   // We'd want something like this for a non-context-sensitive traversal.
734   // However, what we need here is to strip out the saved block in the
735   // Context and use it instead of doing a pointless iteration.
736   // Also, looking for CALL_FT edges in a return is... odd... at best.
737
738   const Block::edgelist &targets = current.loc.block->targets();
739   Block::edgelist::iterator eit = targets.begin();
740   for (; eit != targets.end(); ++eit) {
741     if ((*eit)->type() == CALL_FT) {
742       retBlock = (*eit)->trg();
743       break;
744     }
745   }
746 #endif
747   retBlock = callerCon.front().block;
748   if (!retBlock) {
749     err = true;
750     return false;
751   }
752
753   // Pops absregion and context
754   handleReturnDetails(newElement.reg,
755                       newElement.con);
756   
757   newElement.loc.func = newElement.con.front().func;
758   newElement.loc.block = retBlock;
759   getInsns(newElement.loc);
760   return true;
761 }
762
763 bool Slicer::handleReturnBackward(ParseAPI::Edge *edge,
764         Element &current,
765         Element &newElement,
766         Predicates &p,
767         bool &err)
768 {
769     ParseAPI::Block * callee = edge->src();
770
771     if (followReturn(callee, backward, current, p)) {
772         if (!callee) {
773             err = true;
774             return false;
775         }
776
777         newElement = current;
778
779         // Update location
780         newElement.loc.block = callee;
781         newElement.loc.func = getEntryFunc(callee);
782         getInsnsBackward(newElement.loc);
783
784         // handleReturnDetailsBackward updates both an AbsRegion and a context
785         if (!handleReturnDetailsBackward(newElement.reg,
786                     newElement.con,
787                     current.loc.block,
788                     newElement.loc.func)) {
789             err = true;
790             return false;
791         }
792         return true;
793     }
794
795     return false;
796 }
797
798 bool Slicer::search(Element &initial,
799                     Elements &succ,
800                     Predicates &p,
801                     Direction dir) {
802   bool ret = true;
803   
804   Assignment::Ptr source = initial.ptr;
805
806   Elements worklist;
807   
808   if (dir == forward)  {
809       slicing_cerr << "\t\t Getting forward successors from " << initial.ptr->format()
810           << " - " << initial.reg.format() << endl;
811   } else {
812       slicing_cerr << "\t\t Getting backward predecessors from " << initial.ptr->format()
813           << " - " << initial.reg.format() << endl;
814   }
815
816   if (!getNextCandidates(initial, worklist, p, dir)) {
817     ret = false;
818   }
819
820   // Need this so we don't get trapped in a loop (literally) 
821   std::set<Address> visited;
822   
823   while (!worklist.empty()) {
824     Element current = worklist.front();
825     worklist.pop();
826
827     if (!current.valid) {
828        // This marks a widen spot
829        succ.push(current);
830        continue;
831     }
832
833     if (visited.find(current.addr()) != visited.end()) {
834       continue;
835     }
836     else {
837       visited.insert(current.addr());
838     }
839     
840     // After this point we treat current as a scratch space to scribble in
841     // and return...
842
843     // Split the instruction up
844     std::vector<Assignment::Ptr> assignments;
845     Instruction::Ptr insn;
846     if (dir == forward)
847         insn = current.loc.current->first;
848     else
849         insn = current.loc.rcurrent->first;
850     convertInstruction(insn,
851                        current.addr(),
852                        current.loc.func,
853                        assignments);
854     bool keepGoing = true;
855
856     for (std::vector<Assignment::Ptr>::iterator iter = assignments.begin();
857          iter != assignments.end(); ++iter) {
858       Assignment::Ptr &assign = *iter;
859
860       findMatches(current, assign, dir, p, succ);
861
862       if (kills(current, assign)) {
863         keepGoing = false;
864       }
865     }
866     if (keepGoing) {
867       if (!getNextCandidates(current, worklist, p, dir)) {
868         ret = false;
869       }
870     }
871   }
872   return ret;
873 }
874
875 bool Slicer::getNextCandidates(Element &current, Elements &worklist,
876                                Predicates &p, Direction dir) {
877   if (dir == forward) {
878     return getSuccessors(current, worklist, p);
879   }
880   else {
881     return getPredecessors(current, worklist, p);
882   }
883 }
884
885 bool Slicer::findMatches(Element &current, Assignment::Ptr &assign, Direction dir, Predicates &p, Elements &succ) {
886   if (dir == forward) {
887     // We compare the AbsRegion in current to the inputs
888     // of assign
889     for (unsigned k = 0; k < assign->inputs().size(); ++k) {
890       const AbsRegion &uReg = assign->inputs()[k];
891       slicing_cerr << "\t\t\t\t\tComparing current " 
892                    << current.reg.format() << " to candidate "
893                    << uReg.format() << endl;
894       if (current.reg.contains(uReg)) {
895          if (uReg.isImprecise() && !p.allowImprecision()) {
896             // Consider this to be a widen...
897             current.valid = false;
898          }
899          slicing_cerr << "\t\t\t\t\t\tMatch!, adding " << assign->format() << endl;
900          // We make a copy of each Element for each Assignment...
901          current.ptr = assign;
902          current.inputRegion = uReg;
903          succ.push(current);
904          return true;
905      }
906     }
907   }
908   else {
909     assert(dir == backward);
910     const AbsRegion &oReg = assign->out();
911     slicing_cerr << "\t\t\t\t\tComparing current " 
912                  << current.reg.format() << " to candidate "
913                  << oReg.format() << endl;
914     if (current.reg.contains(oReg)) {
915        if (oReg.isImprecise() && !p.allowImprecision()) {
916           current.valid = false;
917        }
918        slicing_cerr << "\t\t\t\t\t\tMatch!" << endl;
919       current.ptr = assign;
920       current.inputRegion = current.reg;
921       succ.push(current);
922       return true;
923     }
924   }
925   return false;
926 }
927
928 bool Slicer::kills(Element &current, Assignment::Ptr &assign) {
929   // Did we find a definition of the same abstract region?
930   // TBD: overlaps ins't quite the right thing here. "contained
931   // by" would be better, but we need to get the AND/OR
932   // of abslocs hammered out.
933
934   if (assign->out().type() != Absloc::Unknown) {
935     // A region assignment can never kill
936     return false; 
937   }
938
939   return current.reg.contains(assign->out());
940 }
941
942 SliceNode::Ptr Slicer::createNode(Element &elem) {
943   if (created_.find(elem.ptr) != created_.end()) {
944     return created_[elem.ptr];
945   }
946   SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.loc.block, elem.loc.func);
947   created_[elem.ptr] = newNode;
948   return newNode;
949 }
950
951 std::string SliceNode::format() const {
952   if (!a_) {
953     return "<NULL>";
954   }
955
956   stringstream ret;
957   ret << "(" << a_->format() << "@" <<
958     f_->name() << ")";
959   return ret.str();
960 }
961
962 void Slicer::convertInstruction(Instruction::Ptr insn,
963                                 Address addr,
964                                 ParseAPI::Function *func,
965                                 std::vector<Assignment::Ptr> &ret) {
966   converter.convert(insn,
967                     addr,
968                     func,
969                     ret);
970   return;
971 }
972
973 void Slicer::getInsns(Location &loc) {
974
975   InsnCache::iterator iter = insnCache_.find(loc.block);
976   if (iter == insnCache_.end()) {
977     getInsnInstances(loc.block, insnCache_[loc.block]);
978   }
979   
980   loc.current = insnCache_[loc.block].begin();
981   loc.end = insnCache_[loc.block].end();
982 }
983
984 void Slicer::getInsnsBackward(Location &loc) {
985     InsnCache::iterator iter = insnCache_.find(loc.block);
986     if (iter == insnCache_.end()) {
987       getInsnInstances(loc.block, insnCache_[loc.block]);
988     }
989
990     loc.rcurrent = insnCache_[loc.block].rbegin();
991     loc.rend = insnCache_[loc.block].rend();
992 }
993
994 void Slicer::insertPair(Graph::Ptr ret,
995                         Direction dir,
996                         Element &source,
997                         Element &target) {
998   SliceNode::Ptr s = createNode(source);
999   SliceNode::Ptr t = createNode(target);
1000
1001   slicing_cerr << "Inserting pair: " << s->format() << ", " << t->format() << endl;
1002   if (dir == forward) {
1003      SliceEdge::Ptr e = SliceEdge::create(s, t, target.inputRegion);
1004      ret->insertPair(s, t, e);
1005   } else {
1006      SliceEdge::Ptr e = SliceEdge::create(t, s, target.inputRegion);
1007      ret->insertPair(t, s, e);
1008   }
1009 }
1010
1011 void Slicer::widen(Graph::Ptr ret,
1012                    Direction dir,
1013                    Element &e) {
1014   if (dir == forward) {
1015     ret->insertPair(createNode(e),
1016                     widenNode());
1017     ret->insertExitNode(widenNode());
1018   }
1019   else {
1020     ret->insertPair(widenNode(), createNode(e));
1021     ret->insertEntryNode(widenNode());
1022   }
1023 }
1024
1025 SliceNode::Ptr Slicer::widenNode() {
1026   if (widen_) {
1027     return widen_;
1028   }
1029
1030   widen_ = SliceNode::create(Assignment::Ptr(),
1031                               NULL, NULL);
1032   return widen_;
1033 }
1034
1035 void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
1036   if (dir == forward) {    
1037     ret->insertExitNode(createNode(e));
1038   }
1039   else {
1040     ret->insertEntryNode(createNode(e));
1041   }
1042 }
1043
1044 void Slicer::fastForward(Location &loc, Address
1045                          addr) {
1046   while ((loc.current != loc.end) &&
1047          (loc.addr() < addr)) {
1048     loc.current++;
1049   }
1050   assert(loc.current != loc.end);
1051   assert(loc.addr() == addr);
1052 }
1053
1054 void Slicer::fastBackward(Location &loc, Address addr) {
1055     while ((loc.rcurrent != loc.rend) &&
1056          (loc.addr() > addr)) {
1057     loc.rcurrent++;
1058   }
1059     
1060   assert(loc.rcurrent != loc.rend);
1061   assert(loc.addr() == addr);  
1062 }
1063
1064 void Slicer::cleanGraph(Graph::Ptr ret) {
1065   slicing_cerr << "Cleaning up the graph..." << endl;
1066   // Clean the graph up
1067   
1068   // TODO: make this more efficient by backwards traversing.
1069   // For now, I know that we're generating graphs with tons of
1070   // unnecessary flag sets (which are immediately killed) and so
1071   // we don't have long non-exiting chains, we have "fuzz"
1072   
1073   NodeIterator nbegin, nend;
1074   ret->allNodes(nbegin, nend);
1075   
1076   std::list<Node::Ptr> toDelete;
1077   
1078   for (; nbegin != nend; ++nbegin) {
1079     SliceNode::Ptr foozle =
1080       dyn_detail::boost::dynamic_pointer_cast<SliceNode>(*nbegin);
1081     //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
1082     if ((*nbegin)->hasOutEdges()) {
1083       slicing_cerr << "\t has out edges, leaving in" << endl;
1084       
1085       // This cleans up case where we ended a backward slice
1086       // but never got to mark the node as an entry node
1087       if (!(*nbegin)->hasInEdges()) {
1088         ret->markAsEntryNode(foozle);
1089       }
1090       continue;
1091     }
1092     if (ret->isExitNode(*nbegin)) {
1093
1094       slicing_cerr << "\t is exit node, leaving in" << endl;
1095       // A very odd case - a graph of 1 node. Yay!
1096       if (!(*nbegin)->hasInEdges()) {
1097         ret->markAsEntryNode(foozle);
1098       }
1099       continue;
1100     }
1101     slicing_cerr << "\t deleting" << endl;
1102     toDelete.push_back(*nbegin);
1103   }
1104
1105   for (std::list<Node::Ptr>::iterator tmp =
1106          toDelete.begin(); tmp != toDelete.end(); ++tmp) {
1107     ret->deleteNode(*tmp);
1108   }
1109 }
1110
1111 bool Slicer::followCall(ParseAPI::Block *target, Direction dir, Element &current, Predicates &p)
1112 {
1113   // We provide the call stack and the potential callee.
1114   // It returns whether we follow the call or not.
1115   
1116   // A NULL callee indicates an indirect call.
1117   // TODO on that one...
1118   
1119   // Find the callee
1120   assert(dir == forward);
1121   ParseAPI::Function *callee = (target ? getEntryFunc(target) : NULL);
1122   // Create a call stack
1123   std::stack<std::pair<ParseAPI::Function *, int> > callStack;
1124   for (Context::reverse_iterator calls = current.con.rbegin();
1125        calls != current.con.rend();
1126        ++calls)
1127     {
1128       if (calls->func)  {
1129         //cerr << "Adding " << calls->func->name() << " to call stack" << endl;
1130         callStack.push(std::make_pair<ParseAPI::Function*, int>(calls->func, calls->stackDepth));
1131       }
1132     }
1133   //cerr << "Calling followCall with stack and " << (callee ? callee->name() : "<NULL>") << endl;
1134   // FIXME: assuming that this is not a PLT function, since I have no idea at present.
1135   // -- BW, April 2010
1136   return p.followCall(callee, callStack, current.reg);
1137 }
1138
1139 std::vector<ParseAPI::Function *> Slicer::followCallBackward(ParseAPI::Block * callerBlock,
1140         Direction dir,
1141         Element &current,
1142         Predicates &p) {
1143     assert(dir == backward);
1144
1145     // Create the call stack
1146     std::stack<std::pair<ParseAPI::Function *, int> > callStack;
1147     for (Context::reverse_iterator calls = current.con.rbegin();
1148             calls != current.con.rend();
1149             ++calls) {
1150         if (calls->func) {
1151             callStack.push(std::make_pair<ParseAPI::Function *, int>(calls->func, calls->stackDepth));
1152         }
1153     }
1154     return p.followCallBackward(callerBlock, callStack, current.reg);
1155 }
1156
1157 bool Slicer::followReturn(ParseAPI::Block *source,
1158                             Direction dir,
1159                             Element &current,
1160                             Predicates &p)
1161 {
1162     assert(dir == backward);
1163     ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
1164     // Create a call stack
1165     std::stack<std::pair<ParseAPI::Function *, int> > callStack;
1166     for (Context::reverse_iterator calls = current.con.rbegin();
1167             calls != current.con.rend();
1168             ++calls) {
1169         if (calls->func) {
1170             callStack.push(std::make_pair<ParseAPI::Function *, int>(calls->func, calls->stackDepth));
1171         }
1172     }
1173     return p.followCall(callee, callStack, current.reg);
1174 }
1175
1176 ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
1177                                    Direction dir) {
1178   return ((dir == forward) ? e->trg() : e->src());
1179 }
1180
1181 bool Slicer::isWidenNode(Node::Ptr n) {
1182   SliceNode::Ptr foozle =
1183     dyn_detail::boost::dynamic_pointer_cast<SliceNode>(n);
1184   if (!foozle) return false;
1185   if (!foozle->assign()) return true;
1186   return false;
1187 }
1188
1189 void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
1190   if (dir == forward) {
1191     // Entry node
1192     ret->insertEntryNode(aP);
1193   }
1194   else {
1195     ret->insertExitNode(aP);
1196   }
1197 }
1198   
1199
1200 void Slicer::constructInitialElement(Element &initial, Direction dir) {
1201   // Cons up the first Element. We need a context, a location, and an
1202   // abstract region
1203   ContextElement context(f_);
1204   initial.con.push_front(ContextElement(f_));
1205   initial.loc = Location(f_, b_);
1206   initial.reg = a_->out();
1207   initial.ptr = a_;
1208
1209   if (dir == forward) {
1210     initial.loc.fwd = true;
1211     getInsns(initial.loc);
1212     fastForward(initial.loc, a_->addr());
1213   }
1214   else {
1215     initial.loc.fwd = false;
1216     getInsnsBackward(initial.loc);
1217     fastBackward(initial.loc, a_->addr());
1218   }
1219 }   
1220