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