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