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