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