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