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