Update copyright to LGPL on all files
[dyninst.git] / depGraphAPI / src / analyzeDDG.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include <map>
33 #include <algorithm>
34 #include <queue>
35
36 #include "analyzeDDG.h"
37
38 #include "Absloc.h"
39 #include "Instruction.h"
40 #include "Operation.h"
41
42 #include "BPatch_basicBlock.h"
43 #include "BPatch_edge.h"
44 #include "BPatch_function.h"
45
46 #include "dyninstAPI/src/stackanalysis.h"
47 #include "dyninstAPI/src/function.h"
48 #include "dyninstAPI/src/image-func.h"
49 #include "dyninstAPI/src/addressSpace.h"
50 #include "Annotatable.h"
51
52 // Prototype intra-function DDG creator
53
54
55
56 // TODO
57 //   Handle calls
58 //     Trust the ABI to start
59 //     Analyze the callee function
60 //   Interprocedural
61
62 using namespace Dyninst;
63 using namespace Dyninst::DepGraphAPI;
64 using namespace Dyninst::InstructionAPI;
65 using namespace std;
66 using namespace dyn_detail::boost;
67
68 AnnotationClass <DDG::Ptr> DDGAnno(std::string("DDGAnno"));
69
70 // Let me take an aside to discuss aliases and the issues they raise.
71 // An alias pair are two abstract locations that can actually "refer" to
72 // the same concrete location. We see this when memory is used, primarily
73 // due to incomplete information. Consider the following example:
74 // 
75 // S1 is an abstract location that refers to stack slot 1.
76 // S* is an abstract location that refers to an unknown slot on the stack.
77 // S* aliases S1 since it _could_ refer to S1. However, it does not
78 // necessarily refer to S1. Similarly, S1 aliases S; if an instruction is
79 // reading from an unknown location on the stack it may read from S1.
80 //
81 // When we build the DDG we need to include edges from all aliases of
82 // a given used absloc. However, this will _excessively_ overapproximate
83 // the DDG. Consider the following:
84 // B = <i1, i2, i3>
85 // i1 defines S*
86 // i2 defines S1
87 // i3 uses S1
88 // i4 uses S2
89 //
90 // Consider i3. It uses S1, and therefore has a dependence on i2. However,
91 // there is no dependence on i1. Conversely, i4 _does_ have a dependence on
92 // i1. 
93 // 
94 // The second example is more complex. 
95 //
96 // B1 = (i1), B2 = (j1), B3 = (k1)
97 // i1 defines S*
98 // j1 defines S1
99 // k1 uses S1
100 // 
101 // Note that k1 here has a dependence on both i1 and j1.
102 //
103 // So our alias handling needs to deal with this. 
104 //
105 // We do so by extending the classic definition of GEN and KILL.
106 //
107 // Recall that dataflow analysis can be put into the following
108 // framework:
109 // OUT(i_j) = GEN(i_j) U (IN(i_j) - KILL(i_j))
110 // 
111 // where the solution to the analysis is the set of OUT(i_j) that 
112 // satisfies the equations given.
113 // 
114 // Classically, we define GEN and KILL as follows:
115 // GEN(i_j) = {i_j} if i_j defines S_k
116 // KILL(i_j) = {i_j}^c if i_j defines S_k (where {x}^c is the complement set of {x})
117 //
118 // These are the GEN and KILL sets of S_k. We now expand that definition. Let
119 // GEN : Absloc -> {Insn} and Kill : Absloc -> {Insn} be maps where the considered
120 // absloc must be explicit (as opposed to implicit, above). We define these as follows:
121 // GEN(i,X) = 
122 //  if X = S_i : S_i = {i}, S = {i}
123 //  if X = X   : S = {i}, S_1 = {i}, ..., S_n = {i}
124 // KILL(i,X) = 
125 //  if X = S_i : {i}^c
126 //  if X = S   : 0
127 //
128 // The final piece of this is an optimization for a "forward" definition. 
129 // A definition of S at i_n is a "forward definition" of S_i if there is no
130 // prior definition of S_i. This matters to us because we create abstract locations
131 // lazily, and thus we won't _have_ an absloc for S_i...
132 // However, consider the following. Let i_n be a forward definition to S_i. Then
133 // IN(i_n, S_i) = OUT(i_{n-1}, S_i) = GEN(i_{n-1},S_i) U (IN(i_{n-2},S_i) - KILL(i_{n-1},S_i))
134 //     Since i_n is a forward definition, then all GEN sets must have come from a 
135 //     definition of S (and therefore GEN(i_j,S_i) = GEN(i_j,S)) and all KILL sets 
136 //     must have come from a kill of S (and are thus empty). Thus, by induction,
137 //     IN(i_n, S_i) = IN(i_n, S). 
138
139
140 DDG::Ptr DDGAnalyzer::analyze() {
141     if (ddg) return ddg;
142
143     if (func_ == NULL) return DDG::Ptr();
144
145     DDG::Ptr *ret;
146     func_->getAnnotation(ret, DDGAnno);
147     if (ret) {
148         ddg = *ret;
149         return ddg;
150     }
151
152     DDGAnalyzer::BlockSet blocks;
153     func_->getCFG()->getAllBasicBlocks(blocks);
154
155     std::vector<DDGAnalyzer::Block *> entry;
156     func_->getCFG()->getEntryBasicBlock(entry);    
157
158     // We build the DDG from reaching definitions performed for
159     // all points (instructions) and program variables. 
160
161     // Create us a DDG
162     ddg = DDG::createGraph(func_);
163
164     // For complexity and efficiency, we perform the initial analysis on
165     // basic blocks and then do intra-block analysis to build the insn-level
166     // DDG. 
167
168     // Initialize GEN and KILL sets for all basic blocks.
169
170     summarizeGenKillSets(blocks);
171
172     // We now have GEN for each block. Propagate reaching
173     // definitions.
174
175     // Generate the reaching defs for each block
176     generateInterBlockReachingDefs(entry[0]);
177
178     //debugBlockDefs();
179
180     // inSets now contains the following:
181     // FOR EACH Absloc A,
182     //   The list of blocks with reaching definitions of A
183
184     // We want to build the subnode-level graph.
185     generateNodes(blocks);
186
187     // And do a final pass over to ensure all nodes are reachable...
188     ddg->insertVirtualEdges();
189
190     return ddg;
191 }
192
193
194 DDGAnalyzer::DDGAnalyzer(Function *f) :
195     func_(f), addr_width(0) {};
196
197
198 /***********************************************************************************
199  ******* PHASE 1 *******************************************************************
200  ***********************************************************************************/
201
202
203 // Copied from above
204 // GEN(i,X) = 
205 //  if X = S_i : S_i = {i}, S = {i}
206 //  if X = X   : S = {i}, S_1 = {i}, ..., S_n = {i}
207 // KILL(i,X) = 
208 //  if X = S_i : S_i = {i}^c, S = 0
209 //  if X = S   : 0
210
211 // Summarize gen and kill set information for the whole function.
212 // Recurses to summarizeBlockGenKill, below.
213
214 void DDGAnalyzer::summarizeGenKillSets(const BlockSet &blocks) {
215     // Assert we haven't been run before...
216     assert(allGens.empty());
217     //fprintf(stderr, "initializeGenKillSets:\n");
218
219     for (BlockSet::const_iterator iter = blocks.begin();
220          iter != blocks.end(); 
221          ++iter) {
222         Block *curBlock = *iter;
223
224         //fprintf(stderr, "\t Block 0x%lx\n", curBlock->getStartAddress());
225
226         summarizeBlockGenKill(curBlock);
227     }
228 }
229
230 void DDGAnalyzer::summarizeBlockGenKill(Block *curBlock) {
231     std::vector<std::pair<InsnPtr,Address> > insns;
232     curBlock->getInstructions(insns);
233     
234     for (std::vector<std::pair<InsnPtr,Address> >::reverse_iterator i = insns.rbegin();
235          i != insns.rend(); 
236          ++i) {
237         const DefSet &writtenAbslocs = getDefinedAbslocs(i->first, i->second);
238
239         //fprintf(stderr, "Insn at 0x%lx\n", i->second);
240         
241         for (DefSet::iterator iter = writtenAbslocs.begin();
242              iter != writtenAbslocs.end();
243              ++iter) {                
244             // We have two cases: if the absloc is precise or an alias (S_i vs S above)
245             AbslocPtr D = *iter;
246             //fprintf(stderr, "\t%s, %d\n", D->format().c_str(), allKills[curBlock][D]);
247             if (allKills[curBlock][D]) {
248                 // We have already definitely defined
249                 // this absloc (as it was killed), so
250                 // don't do anything else.
251                 continue;
252             }
253
254             cNode cnode = cNode(i->second, D);
255             updateDefSet(D, allGens[curBlock], cnode);
256             updateKillSet(D, allKills[curBlock]);
257         }
258
259         // If we have a call instruction handle the effects of the callee
260         // after the call instruction itself. This will either create
261         // a set of gens and kills based on the ABI or will actually
262         // analyze the callee. 
263         if (isCall(i->first)) {
264             summarizeCallGenKill(i->first, 
265                                  i->second, 
266                                  allGens[curBlock],
267                                  allKills[curBlock]);
268         }
269     }
270 }
271
272 // We still handle aliases by adding a definition for anything
273 // they alias to... 
274 void DDGAnalyzer::updateDefSet(const AbslocPtr D,
275                                DefMap &defMap,
276                                cNode &cnode) {
277     AbslocSet aliases = D->getAliases();
278
279     defMap[D].insert(cnode);
280
281     for (AbslocSet::iterator al = aliases.begin();
282          al != aliases.end(); ++al) {
283         // This handles both the S case if we have a precise
284         // absloc, as well as S_1, ..., S_n if we have an imprecise
285         // absloc. 
286         defMap[*al].insert(cnode);
287     }
288 }
289
290
291 // This function does the work of handling aliases...                    
292
293 void DDGAnalyzer::updateKillSet(const AbslocPtr D,
294                                 KillMap &kills) {
295     if (D->isPrecise()) {
296         // We also record that this block kills this absLoc.
297         // It doesn't matter which instruction does it, since
298         // that will be summarized in the gen information.
299         kills[D] = true;
300     }
301 }
302
303 void DDGAnalyzer::summarizeCallGenKill(const InsnPtr,
304                                        const Address &addr,
305                                        DefMap &gens,
306                                        KillMap &kills) {
307     // I know of no architecture where the call instruction is 1 byte. 
308     // So let's use call+1 as a placeholder for the effects of the call.
309     
310     Address placeholder = addr+1;
311
312     // This will eventually make the decision of which mechanism to use to 
313     // summarize the call. 
314
315     Function *callee = getCallee(addr);
316
317     summarizeABIGenKill(placeholder, callee, gens, kills);
318
319     // summarizeConservativeGenKill(gens, kills);
320     // summarizeScanGenKill(callee, gens, kills);
321     // summarizeAnalyzeGenKill(callee, gen, kills);
322
323 }
324
325 /**********************************************************************
326  ******** PHASE 2 *****************************************************
327  **********************************************************************/
328
329
330 void DDGAnalyzer::generateInterBlockReachingDefs(Block *entry) {
331     std::queue<Block *> worklist;
332
333     worklist.push(entry);
334
335     while (!worklist.empty()) {
336         Block *working = worklist.front();
337         worklist.pop();
338
339         //fprintf(stderr, "Considering block 0x%lx\n", working->getStartAddress());
340
341         // Calculate the new in set 
342
343         BlockSet preds;
344         getPredecessors(working, preds);
345         
346         // NEW_IN = U (j \in pred) OUT(j,a)
347         inSets[working].clear();
348         
349         merge(inSets[working], preds);
350
351         //fprintf(stderr, "New in set:\n");
352         //debugDefMap(inSets[working], "\t");
353
354         // Now: newIn = U (j \in pred) OUT(j)
355         
356         // OUT(i,a) = GEN(i,a) U (IN(i,a) - KILL(i,a))
357         DefMap newOut;
358         calcNewOut(newOut,
359                    allGens[working], 
360                    allKills[working],
361                    inSets[working]);
362         //fprintf(stderr, "Old out set: \n");
363         //debugDefMap(outSets[working], "\t");
364
365         //fprintf(stderr, "New out set: \n");
366         //debugDefMap(newOut, "\t");
367
368         if (newOut != outSets[working]) {
369             outSets[working] = newOut;
370             BlockSet successors;
371             getSuccessors(working, successors);
372             for (BlockSet::iterator succ = successors.begin(); succ != successors.end(); ++succ) {
373                 worklist.push(*succ);
374             }
375         }
376     }    
377 }
378
379 // Merge has to do two things. 
380 // First, handle the unknown parameter definition.
381 //   If any of the input blocks define a precise absloc A,
382 //   then we consider all other blocks to have a "parameter"
383 //   definition of A. This parameter definition will later be
384 //   removed if the block actually defines A.
385 // Second, the aliasing problem. 
386 //   If an block defines an abstract region we want to add
387 //   it as a possible definition of everything that it aliases
388 //   to that weren't also definitely defined.
389
390 void DDGAnalyzer::merge(DefMap &target,
391                         const BlockSet &preds) {
392     std::map<Absloc::Ptr, unsigned> beenDefined;
393
394     for (BlockSet::const_iterator iter = preds.begin(); iter != preds.end(); ++iter) {
395         DefMap &source = outSets[*iter];
396         
397         for (DefMap::const_iterator iter = source.begin();
398              iter != source.end(); ++iter) {
399             const Absloc::Ptr A = (*iter).first;
400             
401             target[A].insert(source[A].begin(), source[A].end());
402             beenDefined[A]++;
403             
404             mergeAliases(A, source, target);
405         }
406     }
407     for (std::map<Absloc::Ptr, unsigned>::const_iterator iter = beenDefined.begin();
408          iter != beenDefined.end(); ++iter) {
409         if (iter->second != preds.size())
410             target[iter->first].insert(cNode(0, iter->first, formalParam));
411     }
412
413 }
414
415 void DDGAnalyzer::mergeAliases(const Absloc::Ptr &A,
416                                DefMap &source,
417                                DefMap &target) {
418     if (!A->isPrecise()) {
419         AbslocSet aliases(A->getAliases());
420         
421         for (AbslocSet::iterator a_iter = aliases.begin(); 
422              a_iter != aliases.end(); ++a_iter) {
423             
424             if (source.find(*a_iter) == source.end()) {
425                 target[*a_iter].insert(source[A].begin(), 
426                                        source[A].end());
427             }
428         }
429     }
430 }
431
432
433 void DDGAnalyzer::calcNewOut(DefMap &out,
434                              DefMap &gens,
435                              KillMap &kills,
436                              DefMap &in) {
437     // OUT = GEN U (IN - KILL)
438
439     
440
441     AbslocSet definedAbslocs;
442     for (DefMap::const_iterator iter = gens.begin();
443          iter != gens.end();
444          ++iter) {
445         definedAbslocs.insert((*iter).first);
446     }            
447
448     for (DefMap::const_iterator iter = in.begin(); 
449          iter != in.end();
450          ++iter) {
451         definedAbslocs.insert((*iter).first);
452     }
453
454     // Calculate the new OUT set
455     for (AbslocSet::iterator iter = definedAbslocs.begin();
456          iter != definedAbslocs.end();
457          ++iter) {
458         AbslocPtr A = *iter;
459
460         // If we kill this AbslocPtr within this block, then
461         // take the entry from the GEN set only.
462         if (kills.find(A) != kills.end()) {
463             out[A] = gens[A];
464         }
465         else {
466             // We don't explicitly kill this, so take the union
467             // of local generation with the INs. 
468             out[A] = gens[A];
469             out[A].insert(in[A].begin(), 
470                           in[A].end());
471         }
472     }
473 }
474
475 /**********************************************************************
476  ******** PHASE 3 *****************************************************
477  **********************************************************************/
478
479
480 void DDGAnalyzer::generateNodes(const BlockSet &blocks) {
481     // We have a set of inter-block reaching definitions. We now build the graph
482     // of intra-block reaching defs. 
483     
484     // Algorithmically:
485     // For each block B:
486     //   Let localReachingDefs : Absloc -> Node = ins[B]
487     //   For each instruction instance i in B:
488     //     Let def = i.defines();
489     //     For each absloc D in def:
490     //       Let T = NODE(I,D)
491     //       Let used = abslocs I uses to define D.
492     //       For each absloc U in used:
493     //         Let Aliases = aliases to U.
494     //         For each absloc A in Aliases
495     //           If localReachingDefs[A] neq NULL
496     //             then foreach S in localReachingDefs[A]
497     //               insert(S,T)
498     //           else insert(parameterNode, T)
499     //     For each absloc D in def:
500     //       localReachingDefs[D] = GEN(i) U (localReachingDefs[D] - KILL(i))
501     // See comment below for why we do this in two iterations.
502
503     //fprintf(stderr, "generateIntraBlockReachingDefs...\n");
504
505     for (BlockSet::const_iterator b_iter = blocks.begin();
506          b_iter != blocks.end();
507          ++b_iter) {
508
509         Block *B = *b_iter;
510
511         generateBlockNodes(B);
512
513     }
514 }
515
516 void DDGAnalyzer::generateBlockNodes(Block *B) {
517     std::vector<std::pair<InsnPtr, Address> > insns;
518     B->getInstructions(insns);
519     DefMap &localReachingDefs = inSets[B];
520     //fprintf(stderr, "\tBlock 0x%lx\n", B->getStartAddress());
521     
522     
523     for (unsigned i = 0; i < insns.size(); ++i) {
524         InsnPtr I = insns[i].first;
525         Address addr = insns[i].second;
526         //fprintf(stderr, "\t\t Insn at 0x%lx\n", addr); 
527         
528         DefSet def = getDefinedAbslocs(I, addr);
529
530         createInsnNodes(I, addr, 
531                         def,
532                         localReachingDefs);
533
534         updateReachingDefs(addr, 
535                            def,
536                            localReachingDefs);
537
538         //fprintf(stderr, "After 0x%lx, localReachingDefs:\n",
539         //        addr);
540         //debugDefMap(localReachingDefs, "\t");
541         
542         if (isCall(I)) {
543             // Therefore we don't need to care about localReachingDefs
544             // anymore since it will be disassembled. But we still need
545             // to create nodes.
546             createCallNodes(addr, localReachingDefs);
547         }
548         if (isReturn(I)) {
549             // So again we can destroy localReachingDefs to make return nodes.
550             createReturnNodes(addr, localReachingDefs);
551         }
552     }
553 }
554
555 // This is an interesting function. We need to create the "micro-graph" of 
556 // intra-instruction dependencies, and then hook up the entry nodes of that
557 // micro-graph to the appropriate reaching definitions. 
558 //
559 // This gets interesting when instructions define multiple abstract locations. 
560 // For a trivial example, consider the PC. 
561 //
562 // This gets _really_ interesting when some of the definitions by the instruction
563 // depend on other definitions by the instruction. Consider the IA-32 push instruction,
564 // which can be represented as follows:
565 // SP = SP - 4; (assuming stack 'grows' downward)
566 // *SP = <register>
567 //
568 // Note that the "*SP" operand depends on SP, which is updated. Thus, it depends
569 // on SP _as defined by the push_. 
570 //
571 // In a perfect world, there would be a separate library between the DDG and
572 // InstructionAPI that represents these. We're not in a perfect world, so this
573 // function is an approximation. 
574 //
575 // We currently represent common instructions correctly. Everything else gets a
576 // completely interconnected network. This is a safe overapproximation. See
577 // also, rep prefixes. 
578
579
580 void DDGAnalyzer::createInsnNodes(const InsnPtr I, 
581                                   const Address &addr,
582                                   const DefSet &def,
583                                   DefMap &localReachingDefs) {
584     // We first create the micro-graph. Then, for each used, create
585     // edges from reaching defs to "entry node". 
586
587     // This is a map from <used absloc> to <nodes that use that absloc>
588     NodeMap worklist;
589
590     // Non-PC handling section
591     switch(I->getOperation().getID()) {
592     case e_push: {
593         // SP = SP - 4 
594         // *SP = <register>
595  
596         std::vector<Operand> operands;
597         I->getOperands(operands);
598
599         // According to the InstructionAPI, the first operand will be the argument, the second will be ESP.
600         assert(operands.size() == 2);
601
602         // The argument can be any of the following:
603         // 1) a register (push eax);
604         // 2) an immediate value (push $deadbeef)
605         // 3) a memory location. 
606         Absloc::Ptr arg;
607         if (operands[0].readsMemory()) {
608             // Evaluate 
609         }
610         else {
611             std::set<RegisterAST::Ptr> readRegs;
612             operands[0].getReadSet(readRegs);
613             if (!readRegs.empty()) {
614                 RegisterAST::Ptr reg = *(readRegs.begin());
615                 arg = getAbsloc(reg);
616             }
617         }
618         // Otherwise arg defaults to NULL
619
620         std::set<RegisterAST::Ptr> spRegs;
621         operands[1].getReadSet(spRegs);
622         assert(!spRegs.empty());
623         RegisterAST::Ptr sp = *(spRegs.begin());
624
625         handlePushEquivalent(addr, arg, sp, worklist);
626         
627     }
628         break;
629     case e_call: {
630         // This can be seen as a push of the PC...
631
632         // So we need the PC and the SP
633         RegisterAST::Ptr pc;
634         RegisterAST::Ptr sp;
635         std::set<RegisterAST::Ptr> readRegs = I->getOperation().implicitReads();
636         for (std::set<RegisterAST::Ptr>::iterator iter = readRegs.begin(); iter != readRegs.end(); ++iter) {
637             if (RegisterLoc::isSP(*iter))
638                 sp = *iter;
639             else if (RegisterLoc::isPC(*iter))
640                 pc = *iter;
641             else assert(0);
642         }
643         Absloc::Ptr aPC = getAbsloc(pc);
644         handlePushEquivalent(addr, aPC, sp, worklist);
645         break;
646     }
647     case e_pop: {
648         // <reg> = *SP
649         // SP = SP + 4/8
650         // Amusingly... this doesn't have an intra-instruction dependence. It should to enforce
651         // the order that <reg> = *SP happens before SP = SP - 4, but since the input to both 
652         // uses of SP in this case are the, well, input values... no "sideways" edges. 
653         // However, we still special-case it so that SP doesn't depend on the incoming stack value...
654         // Also, we use the same logic for return, defining it as
655         // PC = *SP
656         // SP = SP + 4/8
657
658         // As with push, eSP shows up as operand 1. 
659
660         std::vector<Operand> operands;
661         I->getOperands(operands);
662
663         // According to the InstructionAPI, the first operand will be the explicit register, the second will be ESP.
664         assert(operands.size() == 2);
665
666         std::set<RegisterAST::Ptr> regs;
667         operands[0].getWriteSet(regs);
668         
669         RegisterAST::Ptr reg = *(regs.begin());
670         assert(reg);
671
672         regs.clear();
673
674         operands[1].getReadSet(regs);
675         RegisterAST::Ptr sp = *(regs.begin());
676
677         handlePopEquivalent(addr, reg, sp, worklist);
678     } break;
679     case e_leave: {
680         // a leave is equivalent to:
681         // mov ebp, esp
682         // pop ebp
683         // From a definition POV, we have the following:
684         // SP = BP
685         // BP = *SP
686         
687         // BP    STACK[newSP]
688         //  |    |
689         //  v    v
690         // SP -> BP
691         
692         // This is going to give the stack analysis fits... for now, I think it just reverts the
693         // stack depth to 0. 
694         
695         // Leave has no operands...
696         RegisterAST::Ptr sp;
697         RegisterAST::Ptr bp;
698         std::set<RegisterAST::Ptr> regs = I->getOperation().implicitWrites();
699         for (std::set<RegisterAST::Ptr>::iterator iter = regs.begin(); iter != regs.end(); ++iter) {
700             if (RegisterLoc::isSP(*iter))
701                 sp = *iter;
702             else
703                 bp = *iter;
704         }
705         Absloc::Ptr aSP = getAbsloc(sp);
706         Absloc::Ptr aBP = getAbsloc(bp);
707
708         // We need the stack...
709         Operation::VCSet memReads = I->getOperation().getImplicitMemReads();
710         // Use addr + 1 for now because we need the post-leave stack height...
711         // This works because leave has a size of 1. It's ugly. I should fix this...
712         Absloc::Ptr aStack = getAbsloc(*(memReads.begin()), addr+1);
713
714         //fprintf(stderr, "%s, %s, %s\n", aSP->format().c_str(), aBP->format().c_str(), aStack->format().c_str());
715
716         Node::Ptr nSP = makeNode(cNode(addr, aSP));
717         Node::Ptr nBP = makeNode(cNode(addr, aBP));
718         
719         worklist[aBP].push_back(nSP);
720         worklist[aStack].push_back(nBP);
721         ddg->insertPair(nSP, nBP);
722
723         break;
724     }
725     case e_ret_near:
726     case e_ret_far: {
727         // PC = *SP
728         // SP = SP + 4/8
729         // Like pop, except it's all implicit.
730
731         // So we need the PC and the SP
732         RegisterAST::Ptr pc;
733         RegisterAST::Ptr sp;
734         std::set<RegisterAST::Ptr> regs = I->getOperation().implicitWrites();
735         for (std::set<RegisterAST::Ptr>::iterator iter = regs.begin(); iter != regs.end(); ++iter) {
736             if (RegisterLoc::isSP(*iter))
737                 sp = *iter;
738             else if (RegisterLoc::isPC(*iter))
739                 pc = *iter;
740             else assert(0);
741         }
742         handlePopEquivalent(addr, pc, sp, worklist);
743     }
744         break;
745     case e_xchg: {
746         // xchg defines two abslocs, and uses them as appropriate...
747         AbslocPtr D1;
748         AbslocPtr D2;
749         
750         if (addr == 0x9124d2) {
751             fprintf(stderr, "Here!\n");
752         }
753
754         AbslocSet::iterator iter = def.gprs.begin(); 
755         D1 = *iter;
756         iter++;
757         if (iter != def.gprs.end()) {
758             D2 = *iter;
759         }
760         else {
761             // Check memory
762             assert(!def.mem.empty());
763             AbslocSet::iterator iter2 = def.mem.begin();
764             D2 = *iter2;
765         }
766                 
767         assert(D1);
768         assert(D2);
769             
770         NodePtr T1 = makeNode(cNode(addr, D1));
771         NodePtr T2 = makeNode(cNode(addr, D2));
772         worklist[D1].push_back(T2);
773         worklist[D2].push_back(T1);
774         break;
775         }
776         
777     default:
778         // Assume full intra-dependence of non-flag and non-pc registers. 
779         const AbslocSet &used = getUsedAbslocs(I, addr);
780         for (DefSet::iterator iter = def.beginGprsMem(); iter != def.end(); ++iter) {
781             // This will give us only non-flag and non-PC registers...
782             AbslocPtr D = *iter;
783             NodePtr T = makeNode(cNode(addr, D));
784             for (AbslocSet::const_iterator u_iter = used.begin(); u_iter != used.end(); ++u_iter) {
785                 AbslocPtr U = *u_iter;
786                 worklist[U].push_back(T);
787             }
788         }
789     }
790     // Now for flags...
791     // According to Matt, the easiest way to represent dependencies for flags on 
792     // IA-32/AMD-64 is to have them depend on the inputs to the instruction and 
793     // not the outputs of the instruction; therefore, there's no intra-instruction
794     // dependence. 
795     const AbslocSet &used = getUsedAbslocs(I, addr);
796     for (DefSet::iterator iter = def.beginFlags(); iter != def.end(); ++iter) {
797         AbslocPtr D = *iter;
798         NodePtr T = makeNode(cNode(addr, D));
799         for (AbslocSet::const_iterator u_iter = used.begin(); u_iter != used.end(); ++u_iter) {
800             AbslocPtr U = *u_iter;
801             worklist[U].push_back(T);
802         }
803     }
804
805     // PC-handling section
806     // Most instructions use the PC to set the PC. This includes calls, relative branches,
807     // and the like. So we're basically looking for indirect branches or absolute branches.
808     // (are there absolutes on IA-32?).
809     // Also, conditional branches and the flag registers they use. 
810
811     if (def.defPC()) {
812     // We're some sort of branch...
813         switch(I->getOperation().getID()) {
814             case e_ret_near:
815             case e_ret_far: {
816                 // Read top of stack, define PC
817                 std::set<RegisterAST::Ptr> regs = I->getOperation().implicitReads();
818                 // Only one thing read...
819                 RegisterAST::Ptr sp = *(regs.begin());
820                 Absloc::Ptr aStack = getAbsloc(sp, addr); 
821
822                 Absloc::Ptr aPC = RegisterLoc::makePC();
823                 NodePtr T = makeNode(cNode(addr, aPC));
824                 worklist[aStack].push_back(T);
825                 break;
826             }
827             default:
828                   // Whatever is in the operands gets used... PC gets written
829                    Absloc::Ptr aPC = RegisterLoc::makePC();
830                    NodePtr T = makeNode(cNode(addr, aPC));
831                    std::vector<Operand> operands;
832                    I->getOperands(operands);
833                    for (unsigned i = 0; i < operands.size(); ++i) {
834                        std::set<RegisterAST::Ptr> regs;
835                        operands[i].getWriteSet(regs);
836                        for (std::set<RegisterAST::Ptr>::iterator r_iter = regs.begin();
837                        r_iter != regs.end(); r_iter++) {
838                            Absloc::Ptr a_r = getAbsloc(*r_iter);
839                            worklist[a_r].push_back(T);
840                        }
841                    }
842         }
843     }
844     else {
845         Absloc::Ptr aPC = RegisterLoc::makePC();
846         NodePtr T = makeNode(cNode(addr, aPC));
847         worklist[aPC].push_back(T);
848     }
849
850     
851     
852     //fprintf(stderr, "Creating nodes for addr 0x%lx\n", addr);
853     // And now hook up reaching definitions
854     for (NodeMap::iterator e_iter = worklist.begin(); e_iter != worklist.end(); ++e_iter) {
855         for (NodeVec::iterator n_iter = e_iter->second.begin();
856              n_iter != e_iter->second.end(); ++n_iter) {
857              NodePtr T = *n_iter;
858              //fprintf(stderr, "\tNode %s\n", T->format().c_str());
859              AbslocPtr U = e_iter->first;
860
861              if (localReachingDefs[U].empty()) {
862                 // Not sure this can actually happen...
863                 // Just build a parameter node
864                 cNode tmp(0, U, formalParam);
865                 NodePtr S = makeNode(tmp);
866                 ddg->insertPair(S, T);
867                 //fprintf(stderr, "\t\t from parameter node %s\n", S->format().c_str());
868             }
869             else {
870                 for (cNodeSet::iterator c_iter = localReachingDefs[U].begin();
871                      c_iter != localReachingDefs[U].end(); ++c_iter) {
872                     NodePtr S = makeNode(*c_iter);
873
874                     //fprintf(stderr, "\t\t %s\n", S->format().c_str());
875                     
876                     ddg->insertPair(S,T);
877                     //fprintf(stderr, "\t\t\t\t ... from local definition %s/0x%lx\n",
878                     //c_iter->first->format().c_str(),
879                     //c_iter->second.addr);
880                 }
881             }
882         }
883     }
884 }
885
886 void DDGAnalyzer::updateReachingDefs(const Address &addr, 
887                                      const DefSet &def, 
888                                      DefMap &localReachingDefs) { 
889     // We now update localReachingDefs. If we do it in the previous
890     // loop we can get errors. Consider this example:
891     // 
892     // i1 defines r1, r2, r3
893     // i2 uses r1 and defines r1, r2
894     // 
895     // When at i1 localReachingDefs contains (r1, i1), (r2, i1), (r3, i1)
896     // 
897     // We then consider i2.
898     // Def set: (r1, r2)
899     // Use set: (r1)
900     //
901     // Let D = r1
902     //   Let U = r1
903     //     Insert edge ((i1, r1), (i2, r1))
904     //   Update localReachingDefs (r1, i2), (r2, i1), (r3, i1)
905     // Let D = r2
906     //   Let U = r1
907     //     Insert edge ((i2, r1), (i2, r2))
908     //
909     // See the problem? Because we update localReachingDefs before we're done
910     // with the instruction we can imply an incorrect ordering of assignments
911     // within the instruction. Instead we update localReachingDefs afterwards.
912     
913     // Also, we have to be aware of aliasing issues within the block. 
914
915     for (DefSet::iterator d_iter = def.begin();
916          d_iter != def.end(); ++d_iter) {
917         AbslocPtr D = *d_iter;
918         
919         cNode cnode(addr, D); 
920         
921         if (D->isPrecise()) {
922             // Kill previous definitions
923             // We didn't do this in phase 1 because we
924             // were going backwards. 
925             localReachingDefs[D].clear();
926         }
927         
928         updateDefSet(D, localReachingDefs, cnode);
929     }
930 }
931
932 void DDGAnalyzer::createCallNodes(const Address &A,
933                                   const DefMap &reachingDefs) {
934
935     // I know of no architecture where the call instruction is 1 byte. 
936     // So let's use call+1 as a placeholder for the effects of the call.
937
938     Address placeholder = A+1;
939
940     Function *callee = getCallee(A);
941
942     NodeVec actualParams;
943
944     summarizeABIUsed(placeholder, callee, reachingDefs, actualParams);
945
946     // That created all of the used nodes. Now we need to add all defined
947     // nodes. 
948     
949     // We can ignore updating reachingDefs because we are guaranteeing we're
950     // at the end of the block. So we want to look up (or just re-create)
951     // actualReturn nodes for each of these...
952     
953     // So that we don't work too hard, just cache actualReturnNodes when they're
954     // created and re-use them here. 
955
956     for (cNodeSet::iterator i = actualReturnMap_[placeholder].begin(); 
957          i != actualReturnMap_[placeholder].end(); 
958          ++i) {
959         Node::Ptr T = makeNode(*i);
960
961         for (NodeVec::iterator j = actualParams.begin(); 
962              j != actualParams.end(); ++j) {
963             Node::Ptr S = *j;
964             ddg->insertPair(S, T);
965         }
966     }
967 }
968
969 void DDGAnalyzer::createReturnNodes(const Address &,
970                                     const DefMap &reachingDefs) {
971     // I believe we want to create a return node for each reaching definition
972     // to this point...
973
974     // This is an overapproximation but definitely safe. 
975
976     for (DefMap::const_iterator iter = reachingDefs.begin(); 
977          iter != reachingDefs.end(); ++iter) {
978         Absloc::Ptr a = iter->first;
979         
980         cNode cnode(0, a, formalReturn);
981
982         Node::Ptr T = makeNode(cnode);
983
984         for (cNodeSet::const_iterator c_iter = iter->second.begin();
985              c_iter != iter->second.end(); ++c_iter) {
986             NodePtr S = makeNode(*c_iter);
987             ddg->insertPair(S, T);
988         }
989     }
990 }
991
992 /**********************************************************
993  ********* Absloc creation functions **********************
994  **********************************************************/
995
996 Absloc::Ptr DDGAnalyzer::getAbsloc(const InstructionAPI::Expression::Ptr exp,
997                                    Address addr) {
998     // We want to simplify the expression as much as possible given 
999     // currently known state, and then quantify it as one of the following:
1000     // 
1001     // Stack: a memory access based off the current frame pointer (FP) or
1002     //   stack pointer (SP). If we can determine an offset from the "top"
1003     //   of the stack we create a stack slot location. Otherwise we create
1004     //   a "stack" location that represents all stack locations.
1005     //
1006     // Heap: a memory access to a generic pointer.
1007     //
1008     // Memory: a memory access to a known address. 
1009     //
1010     // TODO: aliasing relations. Aliasing SUCKS. 
1011
1012     // Since we have an Expression as input, we don't have the dereference
1013     // operator.
1014
1015     // Here's the logic:
1016     // If no registers are used:
1017     //   If only immediates are used:
1018     //     Evaluate and create a MemLoc.
1019     //   If a dereference exists:
1020     //     WTF???
1021     // If registers are used:
1022     //   If the only register is the FP AND the function has a stack frame:
1023     //     Set FP to 0, eval, and create a specific StackLoc.
1024     //   If the only register is the SP:
1025     //     If we know the contents of SP:
1026     //       Eval and create a specific StackLoc
1027     //     Else create a generic StackLoc.
1028     //   If a non-stack register is used:
1029     //     Create a generic MemLoc.
1030
1031     long spHeight = 0;
1032     int spRegion = 0;
1033     bool stackExists = getCurrentStackHeight(addr, spHeight, spRegion);
1034
1035     bool frameExists = getCurrentFrameStatus(addr);
1036
1037     bool isStack = false;
1038     bool isFrame = false;
1039
1040     static RegisterAST *spRegs32[2] = {NULL, NULL};
1041     static RegisterAST *fpRegs32[2] = {NULL, NULL};
1042
1043     static RegisterAST *spRegs64[2] = {NULL, NULL};
1044     static RegisterAST *fpRegs64[2] = {NULL, NULL};
1045
1046     if (spRegs32[0] == NULL) {
1047         spRegs32[0] = new RegisterAST(r_eSP);
1048         spRegs32[1] = new RegisterAST(r_ESP);
1049
1050         spRegs64[0] = new RegisterAST(r_rSP);
1051         spRegs64[1] = new RegisterAST(r_RSP);
1052
1053         fpRegs32[0] = new RegisterAST(r_eBP);
1054         fpRegs32[1] = new RegisterAST(r_EBP);
1055
1056         fpRegs64[0] = new RegisterAST(r_rBP);
1057         fpRegs64[1] = new RegisterAST(r_RBP);
1058     }
1059
1060     // We currently have to try and bind _every_ _single_ _alias_
1061     // of the stack pointer...
1062     if (stackExists) {
1063         if (exp->bind(spRegs32[0], Result(u32, spHeight)) ||
1064             exp->bind(spRegs32[1], Result(u32, spHeight)) ||
1065             exp->bind(spRegs64[0], Result(u64, spHeight)) ||
1066             exp->bind(spRegs64[1], Result(u64, spHeight))) {
1067             isStack = true;
1068         }
1069     }
1070     if (frameExists) {
1071         if (exp->bind(fpRegs32[0], Result(u32, 0)) ||
1072             exp->bind(fpRegs32[1], Result(u32, 0)) ||
1073             exp->bind(fpRegs64[0], Result(u64, 0)) ||
1074             exp->bind(fpRegs64[1], Result(u64, 0))) {
1075             isFrame = true;
1076         }
1077     }
1078
1079     Result res = exp->eval();
1080
1081     if (!res.defined)
1082         return MemLoc::getMemLoc();
1083     
1084     Address resAddr;
1085     if (!convertResultToAddr(res, resAddr))
1086         return MemLoc::getMemLoc();
1087
1088     if (isStack)
1089         return StackLoc::getStackLoc(resAddr, spRegion);
1090     
1091     // Frame-based accesses are always from region 0...
1092     if (isFrame)
1093         return StackLoc::getStackLoc(resAddr, 0);
1094
1095     return MemLoc::getMemLoc(resAddr);
1096 }
1097
1098
1099 // Things are a lot easier if we know it's a register...
1100 Absloc::Ptr DDGAnalyzer::getAbsloc(const InstructionAPI::RegisterAST::Ptr reg) {
1101     return RegisterLoc::getRegLoc(reg);
1102 }
1103
1104 void DDGAnalyzer::getUsedAbslocs(const InsnPtr insn,
1105                                  Address addr,
1106                                  AbslocSet &uses) {
1107     std::set<RegisterAST::Ptr> regReads;
1108     insn->getReadSet(regReads);
1109
1110     // Registers are nice and easy. The next clause is for memory... now
1111     // that sucks.
1112
1113     for (std::set<RegisterAST::Ptr>::const_iterator r = regReads.begin();
1114          r != regReads.end();
1115          ++r) {
1116         // We have 'used' this Absloc
1117         uses.insert(getAbsloc(*r));
1118     }
1119
1120     // Also handle memory writes
1121     if (insn->readsMemory()) {
1122         std::set<Expression::Ptr> memReads;
1123         insn->getMemoryReadOperands(memReads);
1124         for (std::set<Expression::Ptr>::const_iterator r = memReads.begin();
1125              r != memReads.end();
1126              ++r) {
1127             uses.insert(getAbsloc(*r, addr));
1128         }
1129     }
1130 }
1131
1132 void DDGAnalyzer::getDefinedAbslocsInt(const InsnPtr insn,
1133                                        Address addr,
1134                                        DefSet &defs) {
1135     std::set<RegisterAST::Ptr> regWrites;
1136     insn->getWriteSet(regWrites);            
1137
1138     // Registers are nice and easy. The next clause is for memory... now
1139     // that sucks.
1140     
1141     for (std::set<RegisterAST::Ptr>::const_iterator w = regWrites.begin();
1142          w != regWrites.end();
1143          ++w) {
1144         Absloc::Ptr a = getAbsloc(*w);
1145         RegisterLoc::Ptr r = dynamic_pointer_cast<RegisterLoc>(a);
1146         if (r->isFlag())
1147             defs.flags.insert(a);
1148         else if (r->isPC()) {
1149             defs.sprs.insert(a);
1150             defs.defPC_ = true;
1151         }
1152         else 
1153             defs.gprs.insert(a);
1154     }
1155
1156     if (!defs.defPC_) {
1157 // InstructionAPI doesn't explicitly present PC writes in normal fall-through
1158 // execution. We can safely assume that all instructions update the PC, though...
1159         defs.sprs.insert(RegisterLoc::makePC());
1160     }
1161
1162     // Also handle memory writes
1163     if (insn->writesMemory()) {
1164         std::set<Expression::Ptr> memWrites;
1165         insn->getMemoryWriteOperands(memWrites);
1166         for (std::set<Expression::Ptr>::const_iterator w = memWrites.begin();
1167              w != memWrites.end();
1168              ++w) {
1169             // A memory write. Who knew?
1170             Absloc::Ptr A = getAbsloc(*w, addr);
1171             defs.mem.insert(A);
1172         }
1173     }
1174 }
1175
1176 bool DDGAnalyzer::getCurrentStackHeight(Address addr,
1177                                         long &height,
1178                                         int &region) {
1179     StackAnalysis sA(func_->lowlevel_func()->ifunc());
1180     const Dyninst::StackAnalysis::HeightTree *hT = sA.heightIntervals();
1181     
1182     StackAnalysis::Height heightSA;
1183     
1184     Offset off = func_->lowlevel_func()->addrToOffset(addr);
1185     
1186     if (!hT->find(off, heightSA)) {
1187         return false;
1188     }
1189
1190     // Ensure that analysis has been performed.
1191     assert(!heightSA.isTop());
1192
1193     if (heightSA.isBottom()) {
1194         return false;
1195     }
1196
1197     height = heightSA.height();
1198     region = heightSA.region()->name();
1199
1200     return true;
1201 }
1202
1203 bool DDGAnalyzer::convertResultToAddr(const InstructionAPI::Result &res, Address &addr) {
1204     assert(res.defined);
1205     switch (res.type) {
1206     case u8:
1207         addr = (Address) res.val.u8val;
1208         return true;
1209     case s8:
1210         addr = (Address) res.val.s8val;
1211         return true;
1212     case u16:
1213         addr = (Address) res.val.u16val;
1214         return true;
1215     case s16:
1216         addr = (Address) res.val.s16val;
1217         return true;
1218     case u32:
1219         addr = (Address) res.val.u32val;
1220         return true;
1221     case s32:
1222         addr = (Address) res.val.s32val;
1223         return true;
1224     case u48:
1225         addr = (Address) res.val.u48val;
1226         return true;
1227     case s48:
1228         addr = (Address) res.val.s48val;
1229         return true;
1230     case u64:
1231         addr = (Address) res.val.u64val;
1232         return true;
1233     case s64:
1234         addr = (Address) res.val.s64val;
1235         return true;
1236     default:
1237         return false;
1238     }
1239 }
1240
1241 bool DDGAnalyzer::convertResultToSlot(const InstructionAPI::Result &res, int &addr) {
1242     assert(res.defined);
1243     switch (res.type) {
1244     case u8:
1245         addr = (int) res.val.u8val;
1246         return true;
1247     case s8:
1248         addr = (int) res.val.s8val;
1249         return true;
1250     case u16:
1251         addr = (int) res.val.u16val;
1252         return true;
1253     case s16:
1254         addr = (int) res.val.s16val;
1255         return true;
1256     case u32:
1257         addr = (int) res.val.u32val;
1258         return true;
1259     case s32:
1260         addr = (int) res.val.s32val;
1261         return true;
1262         // I'm leaving these in because they may get used, but
1263         // we're definitely truncating them down.
1264     case u48:
1265         addr = (int) res.val.u48val;
1266         return true;
1267     case s48:
1268         addr = (int) res.val.s48val;
1269         return true;
1270     case u64:
1271         addr = (int) res.val.u64val;
1272         return true;
1273     case s64:
1274         addr = (int) res.val.s64val;
1275         return true;
1276     default:
1277         return false;
1278     }
1279 }
1280
1281 bool DDGAnalyzer::getCurrentFrameStatus(Address addr) {
1282     StackAnalysis sA(func_->lowlevel_func()->ifunc()); 
1283     
1284     const Dyninst::StackAnalysis::PresenceTree *pT = sA.presenceIntervals();
1285     Dyninst::StackAnalysis::Presence exists;
1286
1287     Offset off = func_->lowlevel_func()->addrToOffset(addr);
1288
1289     if (!pT->find(off, exists)) return false;
1290
1291     assert(!exists.isTop());
1292
1293     return (exists.presence() == StackAnalysis::Presence::frame_t);
1294 }
1295
1296 /**********************************************************
1297  ********* Utility functions ******************************
1298  **********************************************************/
1299
1300 void DDGAnalyzer::getPredecessors(Block *block,
1301                                   BlockSet &preds) {
1302     std::vector<BPatch_edge *> incEdges;
1303     block->getIncomingEdges(incEdges);
1304     for (unsigned i = 0; i < incEdges.size(); ++i) {
1305         preds.insert(incEdges[i]->getSource());
1306     }
1307 }
1308
1309 void DDGAnalyzer::getSuccessors(Block *block,
1310                                 BlockSet &succs) {
1311     std::vector<BPatch_edge *> outEdges;
1312     block->getOutgoingEdges(outEdges);
1313     for (unsigned i = 0; i < outEdges.size(); ++i) {
1314         succs.insert(outEdges[i]->getTarget());
1315     }
1316 }
1317
1318 Node::Ptr DDGAnalyzer::makeNode(const cNode &cnode) {
1319     // We have our internal information about a graph node;
1320     // now make a real node from it. 
1321
1322     if (nodeMap.find(cnode) == nodeMap.end()) {
1323         switch(cnode.type) {
1324         case normal:
1325             nodeMap[cnode] = OperationNode::createNode(cnode.addr, cnode.absloc);
1326             break;
1327         case formalParam: {
1328             Node::Ptr n = FormalParamNode::createNode(cnode.absloc);
1329             nodeMap[cnode] = n;
1330             ddg->insertFormalParamNode(n);
1331             break;
1332         }
1333         case formalReturn: {
1334             Node::Ptr n = FormalReturnNode::createNode(cnode.absloc);
1335             nodeMap[cnode] = n;
1336             ddg->insertFormalReturnNode(n);
1337             break;
1338         }
1339         case actualParam: {
1340             Node::Ptr n = ActualParamNode::createNode(cnode.addr, cnode.func, cnode.absloc);
1341             nodeMap[cnode] = n;
1342             ddg->insertActualParamNode(n);
1343             break;
1344         }
1345         case actualReturn: {
1346             Node::Ptr n = ActualReturnNode::createNode(cnode.addr, cnode.func, cnode.absloc);
1347             nodeMap[cnode] = n;
1348             ddg->insertActualReturnNode(n);
1349             break;
1350         }
1351         default:
1352             assert(0);
1353             break;
1354         }
1355     }
1356     return nodeMap[cnode];
1357 }
1358
1359 bool DDGAnalyzer::isCall(InsnPtr i) const {
1360     entryID what = i->getOperation().getID();
1361     return (what == e_call);
1362 }
1363  
1364 bool DDGAnalyzer::isReturn(InsnPtr i) const {
1365     entryID what = i->getOperation().getID();
1366     return ((what == e_ret_far) ||
1367             (what == e_ret_near));
1368 }
1369
1370 const DDGAnalyzer::DefSet &DDGAnalyzer::getDefinedAbslocs(const InsnPtr insn,
1371                                                           const Address &a) {
1372     if (defCache.find(a) == defCache.end()) {
1373         assert(defCache.find(a) == defCache.end());
1374         getDefinedAbslocsInt(insn, a, defCache[a]);
1375     }
1376     return defCache[a];
1377 }
1378
1379 const DDGAnalyzer::AbslocSet &DDGAnalyzer::getUsedAbslocs(const InsnPtr insn,
1380                                                           const Address &a) {
1381     if (globalUsed.find(a) == globalUsed.end()) {
1382         getUsedAbslocs(insn, a, globalUsed[a]);
1383     }
1384     return globalUsed[a];
1385 }
1386
1387                                               
1388 DDGAnalyzer::Function *DDGAnalyzer::getCallee(const Address &a) {
1389     // This is hardcore BPatch_function specific. FIXME...
1390
1391     std::vector<BPatch_point *> *points = func_->findPoint(BPatch_subroutine);
1392     for (unsigned i = 0; i < points->size(); ++i) {
1393         if ((*points)[i]->getAddress() == (void *) a) {
1394             return (*points)[i]->getCalledFunction();
1395         }
1396     }
1397     return NULL;
1398 }
1399
1400 InstructionAPI::RegisterAST::Ptr DDGAnalyzer::makeRegister(int id) {
1401     return InstructionAPI::RegisterAST::Ptr(new InstructionAPI::RegisterAST(id));
1402 }
1403
1404
1405 /**********************************************************
1406  ********* Debug functions ********************************
1407  **********************************************************/
1408
1409 void DDGAnalyzer::debugAbslocSet(const AbslocSet &a,
1410                                  char *str) {
1411     fprintf(stderr, "%s Abslocs:\n", str);
1412     for (AbslocSet::const_iterator iter = a.begin();
1413          iter != a.end();
1414          ++iter) {
1415         fprintf(stderr, "%s\t %s\n", str, (*iter)->format().c_str());
1416     }
1417 }
1418
1419 void DDGAnalyzer::debugDefMap(const DefMap &d,
1420                               char *str) {
1421     fprintf(stderr, "%s Abslocs:\n", str);
1422     for (DefMap::const_iterator i = d.begin();
1423          i != d.end();
1424          ++i) {
1425         fprintf(stderr, "%s\t%s\n", 
1426                 str, 
1427                 (*i).first->format().c_str());
1428         for (cNodeSet::const_iterator j = (*i).second.begin();
1429              j != (*i).second.end(); ++j) {
1430             const cNode &c = (*j);
1431             fprintf(stderr, "%s\t\t%s, 0x%lx\n",
1432                     str,
1433                     c.absloc->format().c_str(),
1434                     c.addr);
1435         }
1436     }
1437 }
1438
1439 void DDGAnalyzer::debugLocalSet(const DefMap &s,
1440                                 char *str) {
1441     for (DefMap::const_iterator iter = s.begin();
1442          iter != s.end(); 
1443          ++iter) {
1444         fprintf(stderr, "%s Absloc: %s\n", str, (*iter).first->format().c_str());
1445         for (cNodeSet::const_iterator iter2 = (*iter).second.begin();
1446              iter2 != (*iter).second.end();
1447              ++iter2) {
1448             Address addr = (*iter2).addr;
1449             AbslocPtr absloc = (*iter2).absloc;
1450             fprintf(stderr, "%s\t insn addr 0x%lx, Absloc %s\n", 
1451                     str, 
1452                     addr,
1453                     absloc->format().c_str());
1454         }
1455     }
1456 }
1457
1458 void DDGAnalyzer::debugBlockDefs() {
1459     for (ReachingDefsGlobal::iterator iter = inSets.begin(); iter != inSets.end(); iter++) {
1460         fprintf(stderr, "Block 0x%lx (IN)\n", iter->first->getStartAddress());
1461         debugDefMap(iter->second, "\t");
1462     }
1463     for (ReachingDefsGlobal::iterator iter = outSets.begin(); iter != outSets.end(); iter++) {
1464         fprintf(stderr, "Block 0x%lx (OUT)\n", iter->first->getStartAddress());
1465         debugDefMap(iter->second, "\t");
1466     }
1467 }
1468
1469 //////////////////////////////////
1470 //
1471
1472 void DDGAnalyzer::handlePushEquivalent(Address addr,
1473                                        Absloc::Ptr read,
1474                                        RegisterAST::Ptr sp,
1475                                        NodeMap &worklist) {
1476     assert(sp);
1477     // Stack pointer...
1478     AbslocPtr aSP = getAbsloc(sp);
1479     // And top of the stack. 
1480     Absloc::Ptr aStack = getAbsloc(sp, addr);
1481     
1482     // Okay, now what we're writing. We have two: *SP and SP. 
1483     // We can get those pretty easily, since we already have the SP
1484     // register from the above. 
1485     
1486     
1487     // Now do the graphlet. We have the worklist map for "hook this up in 
1488     // the future". That's nice. 
1489     
1490     Node::Ptr nSP = makeNode(cNode(addr, aSP));
1491     Node::Ptr nStack = makeNode(cNode(addr, aStack));
1492     
1493     worklist[aSP].push_back(nSP);
1494     if (read) {
1495         // If we push an immediate this may be nothing...
1496         worklist[read].push_back(nStack);
1497     }
1498     ddg->insertPair(nSP, nStack);
1499 }
1500
1501 void DDGAnalyzer::handlePopEquivalent(Address addr,
1502                                       RegisterAST::Ptr writtenReg,
1503                                       RegisterAST::Ptr sp,
1504                                       NodeMap &worklist) {
1505     assert(writtenReg);
1506     assert(sp);
1507     // Stack pointer...
1508     AbslocPtr aSP = getAbsloc(sp);
1509     // Read register...
1510     AbslocPtr aReg = getAbsloc(writtenReg);
1511     // And top of the stack. 
1512     Absloc::Ptr aStack = getAbsloc(sp, addr);
1513     
1514
1515     // We're reading aStack and aSP to write aReg;
1516     // also, reading aSP to write aSP. 
1517     // No intra- definitions.
1518     
1519     // Now do the graphlet. We have the worklist map for "hook this up in 
1520     // the future". That's nice. 
1521     
1522     Node::Ptr nSP = makeNode(cNode(addr, aSP));
1523     Node::Ptr nReg = makeNode(cNode(addr, aReg));
1524     
1525     worklist[aSP].push_back(nSP);
1526     worklist[aSP].push_back(nReg);
1527     worklist[aStack].push_back(nReg);
1528 }