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