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