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