Several DepGraphAPI fixes, InstructionAPI fixes, and DepGraphAPI enhancements.
[dyninst.git] / depGraphAPI / src / analyzeDDG.C
1 /*
2  * Copyright (c) 2007-2008 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();
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     return ddg;
188 }
189
190
191 DDGAnalyzer::DDGAnalyzer(Function *f) :
192     func_(f), addr_width(0) {};
193
194
195 /***********************************************************************************
196  ******* PHASE 1 *******************************************************************
197  ***********************************************************************************/
198
199
200 // Copied from above
201 // GEN(i,X) = 
202 //  if X = S_i : S_i = {i}, S = {i}
203 //  if X = X   : S = {i}, S_1 = {i}, ..., S_n = {i}
204 // KILL(i,X) = 
205 //  if X = S_i : S_i = {i}^c, S = 0
206 //  if X = S   : 0
207
208 // Summarize gen and kill set information for the whole function.
209 // Recurses to summarizeBlockGenKill, below.
210
211 void DDGAnalyzer::summarizeGenKillSets(const BlockSet &blocks) {
212     // Assert we haven't been run before...
213     assert(allGens.empty());
214     //fprintf(stderr, "initializeGenKillSets:\n");
215
216     for (BlockSet::const_iterator iter = blocks.begin();
217          iter != blocks.end(); 
218          ++iter) {
219         Block *curBlock = *iter;
220
221         //fprintf(stderr, "\t Block 0x%lx\n", curBlock->getStartAddress());
222
223         summarizeBlockGenKill(curBlock);
224     }
225 }
226
227 void DDGAnalyzer::summarizeBlockGenKill(Block *curBlock) {
228     std::vector<std::pair<Insn,Address> > insns;
229     curBlock->getInstructions(insns);
230     
231     for (std::vector<std::pair<Insn,Address> >::reverse_iterator i = insns.rbegin();
232          i != insns.rend(); 
233          ++i) {
234         const DefSet &writtenAbslocs = getDefinedAbslocs(i->first, i->second);
235
236         fprintf(stderr, "Insn at 0x%lx\n", i->second);
237         
238         for (DefSet::iterator iter = writtenAbslocs.begin();
239              iter != writtenAbslocs.end();
240              ++iter) {                
241             // We have two cases: if the absloc is precise or an alias (S_i vs S above)
242             AbslocPtr D = *iter;
243             fprintf(stderr, "\t%s, %d\n", D->format().c_str(), allKills[curBlock][D]);
244             if (allKills[curBlock][D]) {
245                 // We have already definitely defined
246                 // this absloc (as it was killed), so
247                 // don't do anything else.
248                 continue;
249             }
250
251             cNode cnode = cNode(i->second, D);
252             updateDefSet(D, allGens[curBlock], cnode);
253             updateKillSet(D, allKills[curBlock]);
254         }
255
256         // If we have a call instruction handle the effects of the callee
257         // after the call instruction itself. This will either create
258         // a set of gens and kills based on the ABI or will actually
259         // analyze the callee. 
260         if (isCall(i->first)) {
261             summarizeCallGenKill(i->first, 
262                                  i->second, 
263                                  allGens[curBlock],
264                                  allKills[curBlock]);
265         }
266     }
267 }
268
269 // We still handle aliases by adding a definition for anything
270 // they alias to... 
271 void DDGAnalyzer::updateDefSet(const AbslocPtr D,
272                                DefMap &defMap,
273                                cNode &cnode) {
274     AbslocSet aliases = D->getAliases();
275
276     defMap[D].push_back(cnode);
277
278     for (AbslocSet::iterator al = aliases.begin();
279          al != aliases.end(); ++al) {
280         // This handles both the S case if we have a precise
281         // absloc, as well as S_1, ..., S_n if we have an imprecise
282         // absloc. 
283         defMap[*al].push_back(cnode);
284     }
285 }
286
287
288 // This function does the work of handling aliases...                    
289
290 void DDGAnalyzer::updateKillSet(const AbslocPtr D,
291                                 KillMap &kills) {
292     if (D->isPrecise()) {
293         // We also record that this block kills this absLoc.
294         // It doesn't matter which instruction does it, since
295         // that will be summarized in the gen information.
296         kills[D] = true;
297     }
298 }
299
300 void DDGAnalyzer::summarizeCallGenKill(const Insn &,
301                                        const Address &addr,
302                                        DefMap &gens,
303                                        KillMap &kills) {
304     // I know of no architecture where the call instruction is 1 byte. 
305     // So let's use call+1 as a placeholder for the effects of the call.
306     
307     Address placeholder = addr+1;
308
309     // This will eventually make the decision of which mechanism to use to 
310     // summarize the call. 
311
312     Function *callee = getCallee(addr);
313
314     summarizeABIGenKill(placeholder, callee, gens, kills);
315
316     // summarizeConservativeGenKill(gens, kills);
317     // summarizeScanGenKill(callee, gens, kills);
318     // summarizeAnalyzeGenKill(callee, gen, kills);
319
320 }
321
322 /**********************************************************************
323  ******** PHASE 2 *****************************************************
324  **********************************************************************/
325
326
327 void DDGAnalyzer::generateInterBlockReachingDefs(Block *entry) {
328     std::queue<Block *> worklist;
329
330     worklist.push(entry);
331
332     while (!worklist.empty()) {
333         Block *working = worklist.front();
334         worklist.pop();
335
336         fprintf(stderr, "Considering block 0x%lx\n", working->getStartAddress());
337
338         // Calculate the new in set 
339
340         BlockSet preds;
341         getPredecessors(working, preds);
342         
343         // NEW_IN = U (j \in pred) OUT(j,a)
344         inSets[working].clear();
345         
346         merge(inSets[working], preds);
347
348         fprintf(stderr, "New in set:\n");
349         debugDefMap(inSets[working], "\t");
350
351         // Now: newIn = U (j \in pred) OUT(j)
352         
353         // OUT(i,a) = GEN(i,a) U (IN(i,a) - KILL(i,a))
354         DefMap newOut;
355         calcNewOut(newOut,
356                    allGens[working], 
357                    allKills[working],
358                    inSets[working]);
359         fprintf(stderr, "New out set: \n");
360         debugDefMap(newOut, "\t");
361
362         if (newOut != outSets[working]) {
363             outSets[working] = newOut;
364             BlockSet successors;
365             getSuccessors(working, successors);
366             for (BlockSet::iterator succ = successors.begin(); succ != successors.end(); ++succ) {
367                 worklist.push(*succ);
368             }
369         }
370     }    
371 }
372
373 // Merge has to do two things. 
374 // First, handle the unknown parameter definition.
375 //   If any of the input blocks define a precise absloc A,
376 //   then we consider all other blocks to have a "parameter"
377 //   definition of A. This parameter definition will later be
378 //   removed if the block actually defines A.
379 // Second, the aliasing problem. 
380 //   If an block defines an abstract region we want to add
381 //   it as a possible definition of everything that it aliases
382 //   to that weren't also definitely defined.
383
384 void DDGAnalyzer::merge(DefMap &target,
385                         const BlockSet &preds) {
386     fprintf(stderr, "Merge over %d blocks\n", preds.size());
387
388     std::map<Absloc::Ptr, unsigned> beenDefined;
389
390     for (BlockSet::const_iterator iter = preds.begin(); iter != preds.end(); ++iter) {
391         DefMap source = outSets[*iter];
392         
393         for (DefMap::const_iterator iter = source.begin();
394              iter != source.end(); ++iter) {
395             const Absloc::Ptr A = (*iter).first;
396             
397             target[A].insert(target[A].end(), source[A].begin(), source[A].end());
398             beenDefined[A]++;
399             
400             if (!A->isPrecise()) {
401                 AbslocSet aliases = A->getAliases();
402                 
403                 for (AbslocSet::iterator a_iter = aliases.begin(); 
404                      a_iter != aliases.end(); ++a_iter) {
405                     
406                     if (source.find(*a_iter) == source.end()) {
407                         target[*a_iter].insert(target[*a_iter].end(),
408                                                source[A].begin(), 
409                                                source[A].end());
410                     }
411                 }
412             }
413         }
414     }
415     for (std::map<Absloc::Ptr, unsigned>::const_iterator iter = beenDefined.begin();
416          iter != beenDefined.end(); ++iter) {
417         if (iter->second != preds.size())
418             target[iter->first].push_back(cNode(0, iter->first, formalParam));
419     }
420
421 }
422
423 void DDGAnalyzer::calcNewOut(DefMap &out,
424                              DefMap &gens,
425                              KillMap &kills,
426                              DefMap &in) {
427     // OUT = GEN U (IN - KILL)
428
429     
430
431     AbslocSet definedAbslocs;
432     for (DefMap::const_iterator iter = gens.begin();
433          iter != gens.end();
434          ++iter) {
435         definedAbslocs.insert((*iter).first);
436     }            
437
438     for (DefMap::const_iterator iter = in.begin(); 
439          iter != in.end();
440          ++iter) {
441         definedAbslocs.insert((*iter).first);
442     }
443
444     // Calculate the new OUT set
445     for (AbslocSet::iterator iter = definedAbslocs.begin();
446          iter != definedAbslocs.end();
447          ++iter) {
448         AbslocPtr A = *iter;
449
450         // If we kill this AbslocPtr within this block, then
451         // take the entry from the GEN set only.
452         if (kills.find(A) != kills.end()) {
453             out[A] = gens[A];
454         }
455         else {
456             // We don't explicitly kill this, so take the union
457             // of local generation with the INs. 
458             out[A] = gens[A];
459             out[A].insert(out[A].end(),
460                           in[A].begin(), 
461                           in[A].end());
462         }
463     }
464 }
465
466 /**********************************************************************
467  ******** PHASE 3 *****************************************************
468  **********************************************************************/
469
470
471 void DDGAnalyzer::generateNodes(const BlockSet &blocks) {
472     // We have a set of inter-block reaching definitions. We now build the graph
473     // of intra-block reaching defs. 
474     
475     // Algorithmically:
476     // For each block B:
477     //   Let localReachingDefs : Absloc -> Node = ins[B]
478     //   For each instruction instance i in B:
479     //     Let def = i.defines();
480     //     For each absloc D in def:
481     //       Let T = NODE(I,D)
482     //       Let used = abslocs I uses to define D.
483     //       For each absloc U in used:
484     //         Let Aliases = aliases to U.
485     //         For each absloc A in Aliases
486     //           If localReachingDefs[A] neq NULL
487     //             then foreach S in localReachingDefs[A]
488     //               insert(S,T)
489     //           else insert(parameterNode, T)
490     //     For each absloc D in def:
491     //       localReachingDefs[D] = GEN(i) U (localReachingDefs[D] - KILL(i))
492     // See comment below for why we do this in two iterations.
493
494     //fprintf(stderr, "generateIntraBlockReachingDefs...\n");
495
496     for (BlockSet::const_iterator b_iter = blocks.begin();
497          b_iter != blocks.end();
498          ++b_iter) {
499
500         Block *B = *b_iter;
501
502         generateBlockNodes(B);
503
504     }
505 }
506
507 void DDGAnalyzer::generateBlockNodes(Block *B) {
508     std::vector<std::pair<Insn, Address> > insns;
509     B->getInstructions(insns);
510     DefMap &localReachingDefs = inSets[B];
511     //fprintf(stderr, "\tBlock 0x%lx\n", B->getStartAddress());
512     
513     
514     for (unsigned i = 0; i < insns.size(); ++i) {
515         Insn I = insns[i].first;
516         Address addr = insns[i].second;
517         //fprintf(stderr, "\t\t Insn at 0x%lx\n", addr); 
518         
519         DefSet def = getDefinedAbslocs(I, addr);
520
521         createInsnNodes(I, addr, 
522                         def,
523                         localReachingDefs);
524
525         updateReachingDefs(addr, 
526                            def,
527                            localReachingDefs);
528
529         fprintf(stderr, "After 0x%lx, localReachingDefs:\n",
530                 addr);
531         debugDefMap(localReachingDefs, "\t");
532         
533         if (isCall(I)) {
534             // Therefore we don't need to care about localReachingDefs
535             // anymore since it will be disassembled. But we still need
536             // to create nodes.
537             createCallNodes(addr, localReachingDefs);
538         }
539         if (isReturn(I)) {
540             // So again we can destroy localReachingDefs to make return nodes.
541             createReturnNodes(addr, localReachingDefs);
542         }
543     }
544 }
545
546 // This is an interesting function. We need to create the "micro-graph" of 
547 // intra-instruction dependencies, and then hook up the entry nodes of that
548 // micro-graph to the appropriate reaching definitions. 
549 //
550 // This gets interesting when instructions define multiple abstract locations. 
551 // For a trivial example, consider the PC. 
552 //
553 // This gets _really_ interesting when some of the definitions by the instruction
554 // depend on other definitions by the instruction. Consider the IA-32 push instruction,
555 // which can be represented as follows:
556 // SP = SP - 4; (assuming stack 'grows' downward)
557 // *SP = <register>
558 //
559 // Note that the "*SP" operand depends on SP, which is updated. Thus, it depends
560 // on SP _as defined by the push_. 
561 //
562 // In a perfect world, there would be a separate library between the DDG and
563 // InstructionAPI that represents these. We're not in a perfect world, so this
564 // function is an approximation. 
565 //
566 // We currently represent common instructions correctly. Everything else gets a
567 // completely interconnected network. This is a safe overapproximation. See
568 // also, rep prefixes. 
569
570
571 void DDGAnalyzer::createInsnNodes(const Insn &I, 
572                                   const Address &addr,
573                                   const DefSet &def,
574                                   DefMap &localReachingDefs) {
575     // We first create the micro-graph. Then, for each used, create
576     // edges from reaching defs to "entry node". 
577
578     // This is a map from <used absloc> to <nodes that use that absloc>
579     NodeMap worklist;
580
581     bool hasExplicitlyDefinedPC = false;
582
583     
584
585     // Non-PC handling section
586     switch(I.getOperation().getID()) {
587     case e_push: {
588         // SP = SP - 4 
589         // *SP = <register>
590  
591         std::vector<Operand> operands;
592         I.getOperands(operands);
593
594         // According to the InstructionAPI, the first operand will be the explicit register, the second will be ESP.
595         assert(operands.size() == 2);
596
597         std::set<RegisterAST::Ptr> readRegs;
598         operands[0].getReadSet(readRegs);
599         RegisterAST::Ptr reg = *(readRegs.begin());
600
601         readRegs.clear();
602         operands[1].getReadSet(readRegs);
603         RegisterAST::Ptr sp = *(readRegs.begin());
604
605         handlePushEquivalent(addr, reg, sp, worklist);
606         
607     }
608         break;
609     case e_call: {
610         // This can be seen as a push of the PC...
611
612         // So we need the PC and the SP
613         RegisterAST::Ptr pc;
614         RegisterAST::Ptr sp;
615         std::set<RegisterAST::Ptr> readRegs = I.getOperation().implicitReads();
616         for (std::set<RegisterAST::Ptr>::iterator iter = readRegs.begin(); iter != readRegs.end(); ++iter) {
617             if (RegisterLoc::isSP(*iter))
618                 sp = *iter;
619             else if (RegisterLoc::isPC(*iter))
620                 pc = *iter;
621             else assert(0);
622         }
623         handlePushEquivalent(addr, pc, sp, worklist);
624         break;
625     }
626     case e_pop: {
627         // <reg> = *SP
628         // SP = SP + 4/8
629         // Amusingly... this doesn't have an intra-instruction dependence. It should to enforce
630         // the order that <reg> = *SP happens before SP = SP - 4, but since the input to both 
631         // uses of SP in this case are the, well, input values... no "sideways" edges. 
632         // However, we still special-case it so that SP doesn't depend on the incoming stack value...
633         // Also, we use the same logic for return, defining it as
634         // PC = *SP
635         // SP = SP + 4/8
636
637         // As with push, eSP shows up as operand 1. 
638
639         std::vector<Operand> operands;
640         I.getOperands(operands);
641
642         // According to the InstructionAPI, the first operand will be the explicit register, the second will be ESP.
643         assert(operands.size() == 2);
644
645         std::set<RegisterAST::Ptr> regs;
646         operands[0].getWriteSet(regs);
647         
648         RegisterAST::Ptr reg = *(regs.begin());
649         assert(reg);
650
651         regs.clear();
652
653         operands[1].getReadSet(regs);
654         RegisterAST::Ptr sp = *(regs.begin());
655
656         handlePopEquivalent(addr, reg, sp, worklist);
657     } break;
658     case e_leave: {
659         // a leave is equivalent to:
660         // mov ebp, esp
661         // pop ebp
662         // From a definition POV, we have the following:
663         // SP = BP
664         // BP = *SP
665         
666         // BP    STACK[newSP]
667         //  |    |
668         //  v    v
669         // SP -> BP
670         
671         // This is going to give the stack analysis fits... for now, I think it just reverts the
672         // stack depth to 0. 
673         
674         // Leave has no operands...
675         RegisterAST::Ptr sp;
676         RegisterAST::Ptr bp;
677         std::set<RegisterAST::Ptr> regs = I.getOperation().implicitWrites();
678         for (std::set<RegisterAST::Ptr>::iterator iter = regs.begin(); iter != regs.end(); ++iter) {
679             if (RegisterLoc::isSP(*iter))
680                 sp = *iter;
681             else
682                 bp = *iter;
683         }
684         Absloc::Ptr aSP = getAbsloc(sp);
685         Absloc::Ptr aBP = getAbsloc(bp);
686
687         // We need the stack...
688         Operation::VCSet memReads = I.getOperation().getImplicitMemReads();
689         // Use addr + 1 for now because we need the post-leave stack height...
690         // This works because leave has a size of 1. It's ugly. I should fix this...
691         Absloc::Ptr aStack = getAbsloc(*(memReads.begin()), addr+1);
692
693         fprintf(stderr, "%s, %s, %s\n", aSP->format().c_str(), aBP->format().c_str(), aStack->format().c_str());
694
695         Node::Ptr nSP = makeNode(cNode(addr, aSP));
696         Node::Ptr nBP = makeNode(cNode(addr, aBP));
697         
698         worklist[aBP].push_back(nSP);
699         worklist[aStack].push_back(nBP);
700         ddg->insertPair(nSP, nBP);
701
702         break;
703     }
704     case e_ret_near:
705     case e_ret_far: {
706         // PC = *SP
707         // SP = SP + 4/8
708         // Like pop, except it's all implicit.
709
710         // So we need the PC and the SP
711         RegisterAST::Ptr pc;
712         RegisterAST::Ptr sp;
713         std::set<RegisterAST::Ptr> regs = I.getOperation().implicitWrites();
714         for (std::set<RegisterAST::Ptr>::iterator iter = regs.begin(); iter != regs.end(); ++iter) {
715             if (RegisterLoc::isSP(*iter))
716                 sp = *iter;
717             else if (RegisterLoc::isPC(*iter))
718                 pc = *iter;
719             else assert(0);
720         }
721         handlePopEquivalent(addr, pc, sp, worklist);
722     }
723         break;
724         // Mass register save instructions...
725         // pusha
726         // popa...
727     default:
728         // Assume full intra-dependence of non-flag and non-pc registers. 
729         const AbslocSet &used = getUsedAbslocs(I, addr);
730         for (DefSet::iterator iter = def.beginGprsMem(); iter != def.end(); ++iter) {
731             // This will give us only non-flag and non-PC registers...
732             AbslocPtr D = *iter;
733             NodePtr T = makeNode(cNode(addr, D));
734             for (AbslocSet::const_iterator u_iter = used.begin(); u_iter != used.end(); ++u_iter) {
735                 AbslocPtr U = *u_iter;
736                 worklist[U].push_back(T);
737             }
738         }
739     }
740
741     // Now for flags...
742     // According to Matt, the easiest way to represent dependencies for flags on 
743     // IA-32/AMD-64 is to have them depend on the inputs to the instruction and 
744     // not the outputs of the instruction; therefore, there's no intra-instruction
745     // dependence. 
746     const AbslocSet &used = getUsedAbslocs(I, addr);
747     for (DefSet::iterator iter = def.beginFlags(); iter != def.end(); ++iter) {
748         AbslocPtr D = *iter;
749         NodePtr T = makeNode(cNode(addr, D));
750         for (AbslocSet::const_iterator u_iter = used.begin(); u_iter != used.end(); ++u_iter) {
751             AbslocPtr U = *u_iter;
752             worklist[U].push_back(T);
753         }
754     }
755
756     // PC-handling section
757     // TODO FIXME
758     fprintf(stderr, "Creating nodes for addr 0x%lx\n", addr);
759     // And now hook up reaching definitions
760     for (NodeMap::iterator e_iter = worklist.begin(); e_iter != worklist.end(); ++e_iter) {
761         for (NodeVec::iterator n_iter = e_iter->second.begin();
762              n_iter != e_iter->second.end(); ++n_iter) {
763              NodePtr T = *n_iter;
764              fprintf(stderr, "\tNode %s\n", T->format().c_str());
765              AbslocPtr U = e_iter->first;
766
767             if (localReachingDefs[U].empty()) {
768                 // Not sure this can actually happen...
769                 // Just build a parameter node
770                 cNode tmp(0, U, formalParam);
771                 NodePtr S = makeNode(tmp);
772                 ddg->insertEntryNode(S);
773                 ddg->insertPair(S, T);
774                 fprintf(stderr, "\t\t from parameter node %s\n", S->format().c_str());
775             }
776             else {
777                 for (cNodeSet::iterator c_iter = localReachingDefs[U].begin();
778                      c_iter != localReachingDefs[U].end(); ++c_iter) {
779                     NodePtr S = makeNode(*c_iter);
780
781                     fprintf(stderr, "\t\t %s\n", S->format().c_str());
782                     
783                     // Sidestep: if S is a formal parameter node ensure that it's in the
784                     // set of entry nodes.
785                     if (c_iter->type == formalParam)
786                         ddg->insertEntryNode(S);
787                     
788                     ddg->insertPair(S,T);
789                     //fprintf(stderr, "\t\t\t\t ... from local definition %s/0x%lx\n",
790                     //c_iter->first->format().c_str(),
791                     //c_iter->second.addr);
792                 }
793             }
794         }
795     }
796 }
797
798 void DDGAnalyzer::updateReachingDefs(const Address &addr,
799                                      const DefSet &def,
800                                      DefMap &localReachingDefs) {
801     // We now update localReachingDefs. If we do it in the previous
802     // loop we can get errors. Consider this example:
803     // 
804     // i1 defines r1, r2, r3
805     // i2 uses r1 and defines r1, r2
806     // 
807     // When at i1 localReachingDefs contains (r1, i1), (r2, i1), (r3, i1)
808     // 
809     // We then consider i2.
810     // Def set: (r1, r2)
811     // Use set: (r1)
812     //
813     // Let D = r1
814     //   Let U = r1
815     //     Insert edge ((i1, r1), (i2, r1))
816     //   Update localReachingDefs (r1, i2), (r2, i1), (r3, i1)
817     // Let D = r2
818     //   Let U = r1
819     //     Insert edge ((i2, r1), (i2, r2))
820     //
821     // See the problem? Because we update localReachingDefs before we're done
822     // with the instruction we can imply an incorrect ordering of assignments
823     // within the instruction. Instead we update localReachingDefs afterwards.
824     
825     // Also, we have to be aware of aliasing issues within the block. 
826
827     for (DefSet::iterator d_iter = def.begin();
828          d_iter != def.end(); ++d_iter) {
829         AbslocPtr D = *d_iter;
830         
831         cNode cnode(addr, D); 
832         
833         if (D->isPrecise()) {
834             // Kill previous definitions
835             // We didn't do this in phase 1 because we
836             // were going backwards. 
837             localReachingDefs[D].clear();
838         }
839         
840         updateDefSet(D, localReachingDefs, cnode);
841     }
842 }
843
844 void DDGAnalyzer::createCallNodes(const Address &A,
845                                   const DefMap &reachingDefs) {
846
847     // I know of no architecture where the call instruction is 1 byte. 
848     // So let's use call+1 as a placeholder for the effects of the call.
849
850     Address placeholder = A+1;
851
852     Function *callee = getCallee(A);
853
854     NodeVec actualParams;
855
856     summarizeABIUsed(placeholder, callee, reachingDefs, actualParams);
857
858     // That created all of the used nodes. Now we need to add all defined
859     // nodes. 
860     
861     // We can ignore updating reachingDefs because we are guaranteeing we're
862     // at the end of the block. So we want to look up (or just re-create)
863     // actualReturn nodes for each of these...
864     
865     // So that we don't work too hard, just cache actualReturnNodes when they're
866     // created and re-use them here. 
867
868     for (cNodeSet::iterator i = actualReturnMap_[placeholder].begin(); 
869          i != actualReturnMap_[placeholder].end(); 
870          ++i) {
871         Node::Ptr T = makeNode(*i);
872
873         for (NodeVec::iterator j = actualParams.begin(); 
874              j != actualParams.end(); ++j) {
875             Node::Ptr S = *j;
876             ddg->insertPair(S, T);
877         }
878     }
879 }
880
881 void DDGAnalyzer::createReturnNodes(const Address &,
882                                     const DefMap &reachingDefs) {
883     // I believe we want to create a return node for each reaching definition
884     // to this point...
885
886     // This is an overapproximation but definitely safe. 
887
888     for (DefMap::const_iterator iter = reachingDefs.begin(); 
889          iter != reachingDefs.end(); ++iter) {
890         Absloc::Ptr a = iter->first;
891         
892         cNode cnode(0, a, formalReturn);
893
894         Node::Ptr T = makeNode(cnode);
895
896         for (cNodeSet::const_iterator c_iter = iter->second.begin();
897              c_iter != iter->second.end(); ++c_iter) {
898             NodePtr S = makeNode(*c_iter);
899             ddg->insertPair(S, T);
900         }
901     }
902 }
903
904 /**********************************************************
905  ********* Absloc creation functions **********************
906  **********************************************************/
907
908 Absloc::Ptr DDGAnalyzer::getAbsloc(const InstructionAPI::Expression::Ptr exp,
909                                    Address addr) {
910     // We want to simplify the expression as much as possible given 
911     // currently known state, and then quantify it as one of the following:
912     // 
913     // Stack: a memory access based off the current frame pointer (FP) or
914     //   stack pointer (SP). If we can determine an offset from the "top"
915     //   of the stack we create a stack slot location. Otherwise we create
916     //   a "stack" location that represents all stack locations.
917     //
918     // Heap: a memory access to a generic pointer.
919     //
920     // Memory: a memory access to a known address. 
921     //
922     // TODO: aliasing relations. Aliasing SUCKS. 
923
924     // Since we have an Expression as input, we don't have the dereference
925     // operator.
926
927     // Here's the logic:
928     // If no registers are used:
929     //   If only immediates are used:
930     //     Evaluate and create a MemLoc.
931     //   If a dereference exists:
932     //     WTF???
933     // If registers are used:
934     //   If the only register is the FP AND the function has a stack frame:
935     //     Set FP to 0, eval, and create a specific StackLoc.
936     //   If the only register is the SP:
937     //     If we know the contents of SP:
938     //       Eval and create a specific StackLoc
939     //     Else create a generic StackLoc.
940     //   If a non-stack register is used:
941     //     Create a generic MemLoc.
942
943     std::set<InstructionAST::Ptr> regUses;
944     exp->getUses(regUses);
945     
946     // If exp is a register (that is, the original operand was *reg) then 
947     // its use set will currently _not_ include itself. So add it.
948     if (dynamic_pointer_cast<InstructionAPI::RegisterAST>(exp))
949         regUses.insert(exp);
950
951     if (regUses.empty()) {
952         // Case 1: Immediate only.
953         Result res = exp->eval();
954         Address memAddr;
955         if (res.defined && convertResultToAddr(res, memAddr)) {
956             return MemLoc::getMemLoc(memAddr);
957         }
958         else {
959             // Oops...
960             fprintf(stderr, "Memory addr failed eval (1) %d, %s, 0x%lx\n", res.defined, exp->format().c_str(), addr);
961             return MemLoc::getMemLoc();
962         }
963     }
964     else {
965         // We have register uses...
966         bool isStack = false;
967
968         for (std::set<InstructionAST::Ptr>::iterator iter = regUses.begin();
969              iter != regUses.end();
970              ++iter) {
971             if (isStackPointer(*iter, addr)) {
972                 isStack = true;
973                 InstructionAST::Ptr sp = *iter;
974                 bindSP(sp, addr);
975             }
976             else if (isFramePointer(*iter, addr)) {
977                 isStack = true;
978                 InstructionAST::Ptr fp = *iter;
979                 bindFP(fp, addr);
980             }
981         }
982
983         if (isStack) {
984             Result res = exp->eval();
985
986             fprintf(stderr, "Evaluating stack height for addr 0x%lx: ", addr);
987
988             int slot;
989             if (res.defined && convertResultToSlot(res, slot)) {
990                 fprintf(stderr, "%d\n", slot);
991                 return StackLoc::getStackLoc(slot);
992             }
993             else {
994                 fprintf(stderr, "%s\n", "???");
995                 return StackLoc::getStackLoc();
996             }
997         }
998         else {
999             return MemLoc::getMemLoc();
1000         }
1001     }    
1002     assert(0);
1003     return MemLoc::getMemLoc();
1004 }
1005
1006
1007 // Things are a lot easier if we know it's a register...
1008 Absloc::Ptr DDGAnalyzer::getAbsloc(const InstructionAPI::RegisterAST::Ptr reg) {
1009     return RegisterLoc::getRegLoc(reg);
1010 }
1011
1012 void DDGAnalyzer::getUsedAbslocs(const InstructionAPI::Instruction insn,
1013                                  Address addr,
1014                                  AbslocSet &uses) {
1015     std::set<RegisterAST::Ptr> regReads;
1016     insn.getReadSet(regReads);
1017
1018     // Registers are nice and easy. The next clause is for memory... now
1019     // that sucks.
1020
1021     for (std::set<RegisterAST::Ptr>::const_iterator r = regReads.begin();
1022          r != regReads.end();
1023          ++r) {
1024         // We have 'used' this Absloc
1025         uses.insert(getAbsloc(*r));
1026     }
1027
1028     // Also handle memory writes
1029     if (insn.readsMemory()) {
1030         std::set<Expression::Ptr> memReads;
1031         insn.getMemoryReadOperands(memReads);
1032         for (std::set<Expression::Ptr>::const_iterator r = memReads.begin();
1033              r != memReads.end();
1034              ++r) {
1035             uses.insert(getAbsloc(*r, addr));
1036         }
1037     }
1038 }
1039
1040 void DDGAnalyzer::getDefinedAbslocsInt(const InstructionAPI::Instruction insn,
1041                                        Address addr,
1042                                        DefSet &defs) {
1043     std::set<RegisterAST::Ptr> regWrites;
1044     insn.getWriteSet(regWrites);            
1045
1046     // Registers are nice and easy. The next clause is for memory... now
1047     // that sucks.
1048
1049     for (std::set<RegisterAST::Ptr>::const_iterator w = regWrites.begin();
1050          w != regWrites.end();
1051          ++w) {
1052         Absloc::Ptr a = getAbsloc(*w);
1053         RegisterLoc::Ptr r = dynamic_pointer_cast<RegisterLoc>(a);
1054         if (r->isFlag())
1055             defs.flags.insert(a);
1056         else if (r->isPC()) 
1057             defs.sprs.insert(a);
1058         else 
1059             defs.gprs.insert(a);
1060     }
1061
1062     // Also handle memory writes
1063     if (insn.writesMemory()) {
1064         std::set<Expression::Ptr> memWrites;
1065         insn.getMemoryWriteOperands(memWrites);
1066         for (std::set<Expression::Ptr>::const_iterator w = memWrites.begin();
1067              w != memWrites.end();
1068              ++w) {
1069             // A memory write. Who knew?
1070             defs.mem.insert(getAbsloc(*w, addr));
1071         }
1072     }
1073 }
1074
1075 bool DDGAnalyzer::getCurrentStackHeight(Address addr, int &height) {
1076     StackAnalysis sA(func_->lowlevel_func()->ifunc());
1077     const Dyninst::StackAnalysis::HeightTree *hT = sA.heightIntervals();
1078     
1079     StackAnalysis::StackHeight heightSA;
1080     
1081     Offset off = func_->lowlevel_func()->addrToOffset(addr);
1082     
1083     if (!hT->find(off, heightSA)) {
1084         return false;
1085     }
1086
1087     // Ensure that analysis has been performed.
1088     assert(!heightSA.isTop());
1089
1090     if (heightSA.isBottom()) {
1091         return false;
1092     }
1093
1094     height = heightSA.height();
1095
1096     return true;
1097 }
1098
1099 bool DDGAnalyzer::convertResultToAddr(const InstructionAPI::Result &res, Address &addr) {
1100     assert(res.defined);
1101     switch (res.type) {
1102     case u8:
1103         addr = (Address) res.val.u8val;
1104         return true;
1105     case s8:
1106         addr = (Address) res.val.s8val;
1107         return true;
1108     case u16:
1109         addr = (Address) res.val.u16val;
1110         return true;
1111     case s16:
1112         addr = (Address) res.val.s16val;
1113         return true;
1114     case u32:
1115         addr = (Address) res.val.u32val;
1116         return true;
1117     case s32:
1118         addr = (Address) res.val.s32val;
1119         return true;
1120     case u48:
1121         addr = (Address) res.val.u48val;
1122         return true;
1123     case s48:
1124         addr = (Address) res.val.s48val;
1125         return true;
1126     case u64:
1127         addr = (Address) res.val.u64val;
1128         return true;
1129     case s64:
1130         addr = (Address) res.val.s64val;
1131         return true;
1132     default:
1133         return false;
1134     }
1135 }
1136
1137 bool DDGAnalyzer::convertResultToSlot(const InstructionAPI::Result &res, int &addr) {
1138     assert(res.defined);
1139     switch (res.type) {
1140     case u8:
1141         addr = (int) res.val.u8val;
1142         return true;
1143     case s8:
1144         addr = (int) res.val.s8val;
1145         return true;
1146     case u16:
1147         addr = (int) res.val.u16val;
1148         return true;
1149     case s16:
1150         addr = (int) res.val.s16val;
1151         return true;
1152     case u32:
1153         addr = (int) res.val.u32val;
1154         return true;
1155     case s32:
1156         addr = (int) res.val.s32val;
1157         return true;
1158         // I'm leaving these in because they may get used, but
1159         // we're definitely truncating them down.
1160     case u48:
1161         addr = (int) res.val.u48val;
1162         return true;
1163     case s48:
1164         addr = (int) res.val.s48val;
1165         return true;
1166     case u64:
1167         addr = (int) res.val.u64val;
1168         return true;
1169     case s64:
1170         addr = (int) res.val.s64val;
1171         return true;
1172     default:
1173         return false;
1174     }
1175 }
1176
1177 bool DDGAnalyzer::isFramePointer(const InstructionAPI::InstructionAST::Ptr &reg, Address addr) {
1178
1179     InstructionAPI::RegisterAST::Ptr container = dynamic_pointer_cast<InstructionAPI::RegisterAST>(RegisterAST::promote(reg));
1180
1181     if (!container) return false;
1182
1183     if ((container->getID() != InstructionAPI::r_EBP) &&
1184         (container->getID() != InstructionAPI::r_RBP)) 
1185         return false; 
1186    
1187     StackAnalysis sA(func_->lowlevel_func()->ifunc()); 
1188     
1189     const Dyninst::StackAnalysis::PresenceTree *pT = sA.presenceIntervals();
1190     Dyninst::StackAnalysis::StackPresence exists;
1191
1192     Offset off = func_->lowlevel_func()->addrToOffset(addr);
1193
1194     if (!pT->find(off, exists)) return false;
1195
1196     assert(!exists.isTop());
1197
1198     return (exists.presence() == StackAnalysis::StackPresence::frame);
1199 }
1200
1201 bool DDGAnalyzer::isStackPointer(const InstructionAPI::InstructionAST::Ptr &reg, Address) {
1202     InstructionAPI::RegisterAST::Ptr container = dynamic_pointer_cast<InstructionAPI::RegisterAST>(RegisterAST::promote(reg));
1203
1204     if (!container) return false;
1205
1206     if ((container->getID() != InstructionAPI::r_ESP) &&
1207         (container->getID() != InstructionAPI::r_RSP)) 
1208         return false;
1209
1210     return true;
1211 }
1212
1213 // Determine the current value of the FP and "bind" it for later evaluation.
1214 // We can assert here that we were passed the frame pointer (and, for correctness,
1215 // that is currently holding the base of the frame) and then bind it to 0.
1216 void DDGAnalyzer::bindFP(InstructionAPI::InstructionAST::Ptr &reg, Address addr) {
1217     assert(isFramePointer(reg, addr));
1218     
1219     InstructionAPI::RegisterAST::Ptr container = dynamic_pointer_cast<InstructionAPI::RegisterAST>(reg);
1220
1221     if (container->getID() == InstructionAPI::r_EBP) {
1222         InstructionAPI::Result res(InstructionAPI::s32,0);
1223         container->setValue(res);
1224     }
1225     else {
1226         InstructionAPI::Result res(InstructionAPI::s64, 0);
1227         container->setValue(res);
1228     }
1229 }
1230
1231 void DDGAnalyzer::bindSP(InstructionAPI::InstructionAST::Ptr &reg, Address addr) {
1232     assert(isStackPointer(reg, addr));
1233
1234     InstructionAPI::RegisterAST::Ptr container = dynamic_pointer_cast<InstructionAPI::RegisterAST>(reg);
1235
1236     int height = 0;
1237     if (getCurrentStackHeight(addr, height)) {
1238         if (container->getID() == InstructionAPI::r_EBP) {
1239             InstructionAPI::Result res(InstructionAPI::s32, height);
1240             container->setValue(res);
1241         }
1242         else {
1243             InstructionAPI::Result res(InstructionAPI::s64, height);
1244             container->setValue(res);
1245         }
1246     }
1247     return;
1248 }
1249
1250
1251
1252
1253 /**********************************************************
1254  ********* Utility functions ******************************
1255  **********************************************************/
1256
1257 void DDGAnalyzer::getPredecessors(Block *block,
1258                                   BlockSet &preds) {
1259     std::vector<BPatch_edge *> incEdges;
1260     block->getIncomingEdges(incEdges);
1261     for (unsigned i = 0; i < incEdges.size(); ++i) {
1262         preds.insert(incEdges[i]->getSource());
1263     }
1264 }
1265
1266 void DDGAnalyzer::getSuccessors(Block *block,
1267                                 BlockSet &succs) {
1268     std::vector<BPatch_edge *> outEdges;
1269     block->getOutgoingEdges(outEdges);
1270     for (unsigned i = 0; i < outEdges.size(); ++i) {
1271         succs.insert(outEdges[i]->getTarget());
1272     }
1273 }
1274
1275 Node::Ptr DDGAnalyzer::makeNode(const cNode &cnode) {
1276     // We have our internal information about a graph node;
1277     // now make a real node from it. 
1278
1279     if (nodeMap.find(cnode) == nodeMap.end()) {
1280         switch(cnode.type) {
1281         case normal:
1282             nodeMap[cnode] = OperationNode::createNode(cnode.addr, cnode.absloc);
1283             break;
1284         case formalParam:
1285             nodeMap[cnode] = FormalParamNode::createNode(cnode.absloc);
1286             break;
1287         case formalReturn:
1288             nodeMap[cnode] = FormalReturnNode::createNode(cnode.absloc);
1289             break;
1290         case actualParam:
1291             nodeMap[cnode] = ActualParamNode::createNode(cnode.addr, cnode.func, cnode.absloc);
1292             break;
1293         case actualReturn:
1294             nodeMap[cnode] = ActualReturnNode::createNode(cnode.addr, cnode.func, cnode.absloc);
1295             break;
1296         default:
1297             assert(0);
1298             break;
1299         }
1300     }
1301     return nodeMap[cnode];
1302 }
1303
1304 bool DDGAnalyzer::isCall(Insn i) const {
1305     entryID what = i.getOperation().getID();
1306     return (what == e_call);
1307 }
1308  
1309 bool DDGAnalyzer::isReturn(Insn i) const {
1310     entryID what = i.getOperation().getID();
1311     return ((what == e_ret_far) ||
1312             (what == e_ret_near));
1313 }
1314
1315 const DDGAnalyzer::DefSet &DDGAnalyzer::getDefinedAbslocs(const Insn &insn,
1316                                                           const Address &a) {
1317     if (defCache.find(a) == defCache.end()) {
1318         assert(defCache.find(a) == defCache.end());
1319         getDefinedAbslocsInt(insn, a, defCache[a]);
1320     }
1321     return defCache[a];
1322 }
1323
1324 const DDGAnalyzer::AbslocSet &DDGAnalyzer::getUsedAbslocs(const Insn &insn,
1325                                                           const Address &a) {
1326     if (globalUsed.find(a) == globalUsed.end()) {
1327         getUsedAbslocs(insn, a, globalUsed[a]);
1328     }
1329     return globalUsed[a];
1330 }
1331
1332                                               
1333 DDGAnalyzer::Function *DDGAnalyzer::getCallee(const Address &a) {
1334     // This is hardcore BPatch_function specific. FIXME...
1335
1336     std::vector<BPatch_point *> *points = func_->findPoint(BPatch_subroutine);
1337     for (unsigned i = 0; i < points->size(); ++i) {
1338         if ((*points)[i]->getAddress() == (void *) a) {
1339             return (*points)[i]->getCalledFunction();
1340         }
1341     }
1342     return NULL;
1343 }
1344
1345 InstructionAPI::RegisterAST::Ptr DDGAnalyzer::makeRegister(int id) {
1346     return InstructionAPI::RegisterAST::Ptr(new InstructionAPI::RegisterAST(id));
1347 }
1348
1349
1350 /**********************************************************
1351  ********* Debug functions ********************************
1352  **********************************************************/
1353
1354 void DDGAnalyzer::debugAbslocSet(const AbslocSet &a,
1355                                              char *str) {
1356     fprintf(stderr, "%s Abslocs:\n", str);
1357     for (AbslocSet::const_iterator iter = a.begin();
1358          iter != a.end();
1359          ++iter) {
1360         fprintf(stderr, "%s\t %s\n", str, (*iter)->format().c_str());
1361     }
1362 }
1363
1364 void DDGAnalyzer::debugDefMap(const DefMap &d,
1365                               char *str) {
1366     fprintf(stderr, "%s Abslocs:\n", str);
1367     for (DefMap::const_iterator i = d.begin();
1368          i != d.end();
1369          ++i) {
1370         fprintf(stderr, "%s\t%s\n", 
1371                 str, 
1372                 (*i).first->format().c_str());
1373         for (cNodeSet::const_iterator j = (*i).second.begin();
1374              j != (*i).second.end(); ++j) {
1375             const cNode &c = (*j);
1376             fprintf(stderr, "%s\t\t%s, 0x%lx\n",
1377                     str,
1378                     c.absloc->format().c_str(),
1379                     c.addr);
1380         }
1381     }
1382 }
1383
1384 void DDGAnalyzer::debugLocalSet(const DefMap &s,
1385                                 char *str) {
1386     for (DefMap::const_iterator iter = s.begin();
1387          iter != s.end(); 
1388          ++iter) {
1389         fprintf(stderr, "%s Absloc: %s\n", str, (*iter).first->format().c_str());
1390         for (cNodeSet::const_iterator iter2 = (*iter).second.begin();
1391              iter2 != (*iter).second.end();
1392              ++iter2) {
1393             Address addr = (*iter2).addr;
1394             AbslocPtr absloc = (*iter2).absloc;
1395             fprintf(stderr, "%s\t insn addr 0x%lx, Absloc %s\n", 
1396                     str, 
1397                     addr,
1398                     absloc->format().c_str());
1399         }
1400     }
1401 }
1402
1403 void DDGAnalyzer::debugBlockDefs() {
1404     for (ReachingDefsGlobal::iterator iter = inSets.begin(); iter != inSets.end(); iter++) {
1405         fprintf(stderr, "Block 0x%lx (IN)\n", iter->first->getStartAddress());
1406         debugDefMap(iter->second, "\t");
1407     }
1408     for (ReachingDefsGlobal::iterator iter = outSets.begin(); iter != outSets.end(); iter++) {
1409         fprintf(stderr, "Block 0x%lx (OUT)\n", iter->first->getStartAddress());
1410         debugDefMap(iter->second, "\t");
1411     }
1412 }
1413
1414 //////////////////////////////////
1415 //
1416
1417 void DDGAnalyzer::handlePushEquivalent(Address addr,
1418                                        RegisterAST::Ptr readReg,
1419                                        RegisterAST::Ptr sp,
1420                                        NodeMap &worklist) {
1421     // Stack pointer...
1422     AbslocPtr aSP = getAbsloc(sp);
1423     // Read register...
1424     AbslocPtr aReg = getAbsloc(readReg);
1425     // And top of the stack. 
1426     Absloc::Ptr aStack = getAbsloc(sp, addr);
1427     
1428     // Okay, now what we're writing. We have two: *SP and SP. 
1429     // We can get those pretty easily, since we already have the SP
1430     // register from the above. 
1431     
1432     
1433     // Now do the graphlet. We have the worklist map for "hook this up in 
1434     // the future". That's nice. 
1435     
1436     Node::Ptr nSP = makeNode(cNode(addr, aSP));
1437     Node::Ptr nStack = makeNode(cNode(addr, aStack));
1438     
1439     worklist[aSP].push_back(nSP);
1440     worklist[aReg].push_back(nStack);
1441     ddg->insertPair(nSP, nStack);
1442 }
1443
1444 void DDGAnalyzer::handlePopEquivalent(Address addr,
1445                                       RegisterAST::Ptr writtenReg,
1446                                       RegisterAST::Ptr sp,
1447                                       NodeMap &worklist) {
1448     assert(writtenReg);
1449     assert(sp);
1450     // Stack pointer...
1451     AbslocPtr aSP = getAbsloc(sp);
1452     // Read register...
1453     AbslocPtr aReg = getAbsloc(writtenReg);
1454     // And top of the stack. 
1455     Absloc::Ptr aStack = getAbsloc(sp, addr);
1456     
1457
1458     // We're reading aStack and aSP to write aReg;
1459     // also, reading aSP to write aSP. 
1460     // No intra- definitions.
1461     
1462     // Now do the graphlet. We have the worklist map for "hook this up in 
1463     // the future". That's nice. 
1464     
1465     Node::Ptr nSP = makeNode(cNode(addr, aSP));
1466     Node::Ptr nReg = makeNode(cNode(addr, aReg));
1467     
1468     worklist[aSP].push_back(nSP);
1469     worklist[aSP].push_back(nReg);
1470     worklist[aStack].push_back(nReg);
1471 }