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