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