Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / stackanalysis.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 "dyninstAPI/src/function.h"
33 #include "dyninstAPI/src/symtab.h"
34 #include "instPoint.h"
35
36 #include "instructionAPI/h/InstructionDecoder.h"
37 #include "instructionAPI/h/Result.h"
38 #include "instructionAPI/h/Instruction.h"
39
40 #include <queue>
41 #include <vector>
42
43 #include "stackanalysis.h"
44
45 #include "Annotatable.h"
46
47 #include "debug.h"
48
49 using namespace Dyninst;
50 using namespace InstructionAPI;
51
52 const StackAnalysis::Height StackAnalysis::Height::bottom(StackAnalysis::Height::notUnique);
53 const StackAnalysis::Height StackAnalysis::Height::top(StackAnalysis::Height::uninitialized);
54
55 const StackAnalysis::Presence StackAnalysis::Presence::bottom(StackAnalysis::Presence::bottom_t);
56 const StackAnalysis::Presence StackAnalysis::Presence::top(StackAnalysis::Presence::top_t);
57
58 const StackAnalysis::InsnTransferFunc StackAnalysis::InsnTransferFunc::bottom(StackAnalysis::InsnTransferFunc::notUnique, false);
59 const StackAnalysis::InsnTransferFunc StackAnalysis::InsnTransferFunc::top(StackAnalysis::InsnTransferFunc::uninitialized, false);
60
61 const StackAnalysis::BlockTransferFunc StackAnalysis::BlockTransferFunc::bottom(StackAnalysis::BlockTransferFunc::notUnique, false, false);
62 const StackAnalysis::BlockTransferFunc StackAnalysis::BlockTransferFunc::top(StackAnalysis::BlockTransferFunc::uninitialized, false, false);
63
64 const StackAnalysis::BlockTransferFunc StackAnalysis::BlockTransferFunc::initial(0, true, true);
65
66 const StackAnalysis::Range StackAnalysis::defaultRange(std::make_pair(0, 0), 0, 0);
67 const StackAnalysis::Range::range_t StackAnalysis::Range::infinite(std::make_pair(MINLONG, MAXLONG));
68
69 AnnotationClass <StackAnalysis::HeightTree> HeightAnno(std::string("HeightAnno"));
70 AnnotationClass <StackAnalysis::PresenceTree> PresenceAnno(std::string("PresenceAnno"));
71
72
73 //
74 //
75 // Concepts:
76 //
77 // There are three terms we throw around:
78 // 
79 // Stack height: the size of the stack; (cur_stack_ptr - func_start_stack_ptr)
80 // Stack delta: the difference in the size of the stack over the execution of
81 //   a region of code (basic block here). (block_end_stack_ptr - block_start_stack_ptr)
82 // Stack clean: the amount the callee function shifts the stack. This is an x86 idiom.
83 //   On x86 the caller pushes arguments onto the stack (and thus shifts the stack).
84 //   Normally the caller also cleans the stack (that is, removes arguments). However, 
85 //   some callee functions perform this cleaning themselves. We need to account for this
86 //   in our analysis, which otherwise assumes that callee functions don't alter the stack.
87 // 
88
89 bool StackAnalysis::analyze()
90 {
91     //stackanalysis_printf("Beginning stack analysis for function %s\n",
92     //func->symTabName().c_str());
93     blocks = func->blocks();
94     if (blocks.empty()) return false;
95
96     blocks = func->blocks();
97     
98     //stackanalysis_printf("\tSummarizing block effects\n");
99     summarizeBlocks();
100     
101     //stackanalysis_printf("\tPerforming fixpoint analysis\n");
102     fixpoint();
103
104     //stackanalysis_printf("\tCreating interval trees\n");
105     createPresenceIntervals();
106     createHeightIntervals();
107
108     func->addAnnotation(heightIntervals_, HeightAnno);
109     func->addAnnotation(presenceIntervals_, PresenceAnno);
110
111     if (dyn_debug_stackanalysis) {
112         debugHeights();
113         debugPresences();
114     }
115
116     //stackanalysis_printf("Finished stack analysis for function %s\n",
117     //func->symTabName().c_str());
118
119     return true;
120 }
121
122 // We want to create a transfer function for the block as a whole. 
123 // This will allow us to perform our fixpoint calculation over
124 // blocks (thus, O(B^2)) rather than instructions (thus, O(I^2)). 
125 //
126 // Handling the stack height is straightforward. We also accumulate
127 // region changes in terms of a stack of Region objects.
128
129 void StackAnalysis::summarizeBlocks() {
130     // STACK HEIGHT:
131     // Foreach block B:
132     //   Let E = block effect
133     //   Foreach (insn i, offset o) in B:
134     //     Let T = transfer function representing i;
135     //     E = T(E);
136     //     blockToInsnFuncs[B][o] = T;
137     //   blockEffects[B] = E;
138
139     // STACK PRESENCE:
140     // Foreach block B:
141     //   Let d = uninitialized;
142     //   Foreach (insn i, offset o) in B:
143     //     d = change in stack presence at d;
144     //     blockToInsnDeltas[B][o] = d;
145     //   blockHeightDeltas[B] = d;
146
147     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
148         Block *block = *iter;
149
150         // Accumulators. They have the following behavior:
151         // 
152         // New region: add to the end of the regions list
153         // Offset to stack pointer: accumulate to delta.
154         // Setting the stack pointer: zero delta, set set_value.
155         // Creating a stack frame: indicate in presence. 
156         // Destroying a stack frame: indicate in presence. 
157
158         BlockTransferFunc &bFunc = blockEffects[block];
159         Presence &bPresence = blockPresences[block];
160
161         bFunc = BlockTransferFunc::top;
162         bPresence = Presence::top;
163
164         //stackanalysis_printf("\t Block starting at 0x%lx: %s, %s\n", block->firstInsnOffset(),
165         //bPresence.format().c_str(), bFunc.format().c_str());
166
167         std::vector<std::pair<InstructionAPI::Instruction::Ptr, Offset> > instances;
168         block->getInsnInstances(instances);
169
170         for (unsigned j = 0; j < instances.size(); j++) {
171             InstructionAPI::Instruction::Ptr insn = instances[j].first;
172             Offset &off = instances[j].second;
173             Offset next;
174             if (j < (instances.size() - 1)) {
175                 next = instances[j+1].second;
176             }
177             else {
178                 next = block->endOffset();
179             }
180             
181             InsnTransferFunc iFunc;
182             Presence presence;
183
184             computeInsnEffects(block, insn, off, 
185                                iFunc, presence);
186
187             if (iFunc != InsnTransferFunc::top) {
188                 iFunc.apply(bFunc);
189                 blockToInsnFuncs[block][next] = iFunc;
190             }
191             if (presence != Presence::top) {
192                 presence.apply(bPresence); 
193                 blockToInsnPresences[block][next] = presence;
194             }
195             //stackanalysis_printf("\t\t\t At 0x%lx: %s, %s\n",
196             //off, bPresence.format().c_str(), bFunc.format().c_str());
197         }
198         //stackanalysis_printf("\t Block summary for 0x%lx: %s\n", block->firstInsnOffset(), bFunc.format().c_str());
199     }
200 }
201
202
203 void StackAnalysis::fixpoint() {
204
205     std::queue<Block *> worklist;
206
207     worklist.push(func->entryBlock());
208
209     while (!worklist.empty()) {
210         Block *block = worklist.front();
211         //stackanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n", block->firstInsnOffset());
212
213         worklist.pop();
214
215         // Step 1: calculate the meet over the heights of all incoming
216         // intraprocedural blocks.
217
218         std::set<BlockTransferFunc> inEffects;
219         std::set<Presence> inPresences;
220         
221         if (block->isEntryBlock(func)) {
222             // The in height is 0
223             // The set height is... 0
224             // And there is no input region.
225             inEffects.insert(BlockTransferFunc::initial);
226             inPresences.insert(Presence(Presence::noFrame_t));
227             //stackanalysis_printf("\t Primed initial block\n");
228         }
229         else {
230             std::vector<Edge *> inEdges; block->getSources(inEdges);
231             for (unsigned i = 0; i < inEdges.size(); i++) {
232                 Edge *edge = inEdges[i];
233                 if (edge->getType() == ET_CALL) continue;
234                 inEffects.insert(outBlockEffects[edge->getSource()]);
235                 //stackanalysis_printf("\t\t Inserting 0x%lx: %s\n", edge->getSource()->firstInsnOffset(),
236                 //outBlockEffects[edge->getSource()].format().c_str());
237                 inPresences.insert(outBlockPresences[edge->getSource()]);
238             }
239         }
240         
241         BlockTransferFunc newInEffect = meet(inEffects);
242         Presence newInPresence = meet(inPresences);
243
244         //stackanalysis_printf("\t New in meet: %s, %s\n",
245         //newInPresence.format().c_str(),
246         //newInEffect.format().c_str());
247
248         // Step 2: see if the input has changed
249
250         if ((newInEffect == inBlockEffects[block]) &&
251             (newInPresence == inBlockPresences[block])) {
252             // No new work here
253             //stackanalysis_printf("\t ... equal to current, skipping block\n");
254             continue;
255         }
256         
257         //stackanalysis_printf("\t ... inequal to current %s, %s, analyzing block\n",
258         //inBlockPresences[block].format().c_str(),
259         //inBlockEffects[block].format().c_str());
260
261         inBlockEffects[block] = newInEffect;
262         inBlockPresences[block] = newInPresence;
263         
264         // Step 3: calculate our new outs
265         
266         blockEffects[block].apply(newInEffect, 
267                                   outBlockEffects[block]);
268         blockPresences[block].apply(newInPresence,
269                                     outBlockPresences[block]);
270         
271         //stackanalysis_printf("\t ... output from block: %s, %s\n",
272         //outBlockPresences[block].format().c_str(),
273         //outBlockEffects[block].format().c_str());
274
275         // Step 4: push all children on the worklist.
276
277         std::vector<Edge *> outEdges; block->getTargets(outEdges);
278
279         for (unsigned i = 0; i < outEdges.size(); i++) {
280             if (outEdges[i]->getType() == ET_CALL) continue;
281             worklist.push(outEdges[i]->getTarget());
282         }
283     }
284 }
285
286 void StackAnalysis::createPresenceIntervals() {
287     // We now have a summary of the state of the stack at
288     // the entry to each block. We need to push that information
289     // into the block. Assume that frame affecting instructions
290     // are rare, where i_m, i_n affect the stack (m < n). Then
291     // each interval runs from [i_m, i_n) or [i_m, i_{n-1}]. 
292
293     presenceIntervals_ = new PresenceTree();
294
295     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
296         Block *block = *iter;
297
298         //stackanalysis_printf("\t Interval creation (P): visiting block at 0x%lx\n", block->firstInsnOffset());
299         
300         Offset curLB = block->firstInsnOffset();
301         Offset curUB = 0;
302         Presence curPres = inBlockPresences[block];
303
304         // We only cache points where the frame presence changes. 
305         // Therefore, we can simply iterate through them. 
306         for (InsnPresence::iterator iter = blockToInsnPresences[block].begin();
307              iter != blockToInsnPresences[block].end(); iter++) {
308
309             // We've changed the state of the stack pointer. End this interval
310             // and start a new one. 
311             
312             curUB = iter->first;
313             presenceIntervals_->insert(curLB, curUB, curPres);
314
315             curLB = curUB;
316             curPres = iter->second;
317         }
318
319         if (curLB != block->endOffset()) {
320             // Cap off the extent for the current block
321             curUB = block->endOffset();
322             assert(curPres == outBlockPresences[block]);
323             presenceIntervals_->insert(curLB, curUB, curPres);
324         }
325     }
326 }
327
328 void StackAnalysis::createHeightIntervals() {
329     // We now have a summary of the state of the stack at
330     // the entry to each block. We need to push that information
331     // into the block. Assume that frame affecting instructions
332     // are rare, where i_m, i_n affect the stack (m < n). Then
333     // each interval runs from [i_m, i_n) or [i_m, i_{n-1}]. 
334
335     heightIntervals_ = new HeightTree();
336
337     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
338         Block *block = *iter;
339
340         //stackanalysis_printf("\t Interval creation (H): visiting block at 0x%lx\n", block->firstInsnOffset());
341         
342         Offset curLB = block->firstInsnOffset();
343         Offset curUB = 0;
344         BlockTransferFunc curHeight = inBlockEffects[block];
345
346         //stackanalysis_printf("\t\t Block starting state: 0x%lx, %s\n", 
347         //curLB, curHeight.format().c_str());
348
349         // We only cache points where the frame height changes. 
350         // Therefore, we can simply iterate through them. 
351         for (InsnFuncs::iterator iter = blockToInsnFuncs[block].begin();
352              iter != blockToInsnFuncs[block].end(); iter++) {
353
354             // We've changed the state of the stack pointer. End this interval
355             // and start a new one. 
356             
357             curUB = iter->first;
358             
359
360             heightIntervals_->insert(curLB, curUB, 
361                                      Height(curHeight.delta(),
362                                             getRegion(curHeight.ranges())));
363
364             curLB = curUB;
365             // Adjust height
366             iter->second.apply(curHeight);
367
368             //stackanalysis_printf("\t\t Block continuing state: 0x%lx, %s\n", 
369             //curLB, curHeight.format().c_str());
370         }
371
372         if (curLB != block->endOffset()) {
373             // Cap off the extent for the current block
374             curUB = block->endOffset();
375             if (curHeight != outBlockEffects[block]) {
376                 fprintf(stderr, "ERROR: accumulated state not equal to fixpoint state!\n");
377                 fprintf(stderr, "\t %s\n", curHeight.format().c_str());
378                 fprintf(stderr, "\t %s\n", outBlockEffects[block].format().c_str());
379             }
380                         
381             assert(curHeight == outBlockEffects[block]);
382
383             heightIntervals_->insert(curLB, curUB, 
384                                      Height(curHeight.delta(),
385                                             getRegion(curHeight.ranges())));
386         }
387     }
388 }
389
390
391 void StackAnalysis::computeInsnEffects(const Block *block,
392                                        const Instruction::Ptr &insn,
393                                        Offset off,
394                                        InsnTransferFunc &iFunc,
395                                        Presence &pres)
396 {
397     //stackanalysis_printf("\t\tInsn at 0x%lx\n", off); 
398     static Expression::Ptr theStackPtr(new RegisterAST(r_eSP));
399     static Expression::Ptr stackPtr32(new RegisterAST(r_ESP));
400     static Expression::Ptr stackPtr64(new RegisterAST(r_RSP));
401     
402     static Expression::Ptr theFramePtr(new RegisterAST(r_eBP));
403     static Expression::Ptr framePtr32(new RegisterAST(r_EBP));
404     static Expression::Ptr framePtr64(new RegisterAST(r_RBP));
405     
406     //TODO: Integrate entire test into analysis lattice
407     entryID what = insn->getOperation().getID();
408
409     if (insn->isWritten(theFramePtr) || insn->isWritten(framePtr32) || insn->isWritten(framePtr64)) {
410       //stackanalysis_printf("\t\t\t FP written\n");
411         if (what == e_mov &&
412             (insn->isRead(theStackPtr) || insn->isRead(stackPtr32) || insn->isRead(stackPtr64))) {
413           pres = Presence(Presence::frame_t);
414           //stackanalysis_printf("\t\t\t Frame created\n");
415         }
416         else {
417             pres = Presence(Presence::noFrame_t);
418             //stackanalysis_printf("\t\t\t Frame destroyed\n");
419         }
420     }
421
422     if (what == e_call) {
423         pdvector<image_edge *> outs;
424         block->getTargets(outs);
425         for (unsigned i=0; i<outs.size(); i++) {
426             image_edge *cur_edge = outs[i];
427             if (cur_edge->getType() != ET_CALL) 
428                 continue;
429             
430             image_basicBlock *target_bbl = cur_edge->getTarget();
431             image_func *target_func = target_bbl->getEntryFunc();
432             if (!target_func)
433                 continue;
434             Height h = getStackCleanAmount(target_func);
435             if (h == Height::bottom) {
436                 iFunc == InsnTransferFunc::bottom;
437             }
438             else {
439                 iFunc.delta() = h.height();
440             }
441
442             //stackanalysis_printf("\t\t\t Stack height changed by self-cleaning function: %s\n", iFunc.format().c_str());
443             return;
444         }
445         //stackanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
446         return;
447     }
448
449     int word_size = func->img()->getAddressWidth();
450     
451     if(!insn->isWritten(theStackPtr) && !insn->isWritten(stackPtr32)) {
452          return;
453     }
454     int sign = 1;
455     switch(what) {
456     case e_push:
457         sign = -1;
458     case e_pop: {
459         Operand arg = insn->getOperand(0);
460         if (arg.getValue()->eval().defined) {
461             iFunc.delta() = sign * word_size;
462             //stackanalysis_printf("\t\t\t Stack height changed by evaluated push/pop: %s\n", iFunc.format().c_str());
463             return;
464         }
465         iFunc.delta() = sign * arg.getValue()->size();
466         //stackanalysis_printf("\t\t\t Stack height changed by unevalled push/pop: %s\n", iFunc.format().c_str());
467         return;
468     }
469     case e_ret_near:
470     case e_ret_far:
471         iFunc.delta() = word_size;
472         //stackanalysis_printf("\t\t\t Stack height changed by return: %s\n", iFunc.format().c_str());
473         return;
474     case e_sub:
475         sign = -1;
476     case e_add: {
477         // Add/subtract are op0 += (or -=) op1
478         Operand arg = insn->getOperand(1);
479         Result delta = arg.getValue()->eval();
480         if(delta.defined) {
481             switch(delta.type) {
482             case u8:
483                 iFunc.delta() = (sign * delta.val.u8val);
484                 break;
485             case u16:
486                 iFunc.delta() = (sign * delta.val.u16val);
487                 break;
488             case u32:
489                 iFunc.delta() = (sign * delta.val.u32val);
490                 break;
491             case u64:
492                 iFunc.delta() = (sign * delta.val.u64val);
493                 break;
494             case s8:
495                 iFunc.delta() = (sign * delta.val.s8val);
496                 break;
497             case s16:
498                 iFunc.delta() = (sign * delta.val.s16val);
499                 break;
500             case s32:
501                 iFunc.delta() = (sign * delta.val.s32val);
502                 break;
503             case s64:
504                 iFunc.delta() = (sign * delta.val.s64val);
505                 break;
506             default:
507                 // Add of anything that's not a "normal" integral type
508                 // means we don't know what happened
509                 iFunc = InsnTransferFunc::bottom;
510                 break;
511             }
512             //stackanalysis_printf("\t\t\t Stack height changed by evalled add/sub: %s\n", iFunc.format().c_str());
513             return;
514         }
515         iFunc.range() = Range(Range::infinite, 0, off);
516         //stackanalysis_printf("\t\t\t Stack height changed by unevalled add/sub: %s\n", iFunc.format().c_str());
517         return;
518     }
519         // We treat return as zero-modification right now
520     case e_leave:
521         iFunc.abs() = true;
522         iFunc.delta() = 0;
523         //stackanalysis_printf("\t\t\t Stack height reset by leave: %s\n", iFunc.format().c_str());
524         return;
525     default:
526         iFunc.range() = Range(Range::infinite, 0, off);
527         //stackanalysis_printf("\t\t\t Stack height changed by unhandled insn \"%s\": %s\n", 
528         //insn->format().c_str(), iFunc.format().c_str());
529         return;
530     }
531     assert(0);
532     return;
533 }
534
535 StackAnalysis::Height StackAnalysis::getStackCleanAmount(image_func *func) {
536     // Cache previous work...
537     if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
538         return funcCleanAmounts[func];
539     }
540
541     if (!func->cleansOwnStack()) {
542         funcCleanAmounts[func] = 0;
543         return funcCleanAmounts[func];
544     }
545
546     InstructionDecoder decoder;   
547     decoder.setMode(func->img()->getAddressWidth() == 8);
548     unsigned char *cur;
549
550     std::set<Height> returnCleanVals;
551     
552     for (unsigned i=0; i < func->funcExits().size(); i++) {
553         cur = (unsigned char *) func->getPtrToInstruction(func->funcExits()[i]->offset());
554         Instruction::Ptr insn = decoder.decode(cur);
555         
556         entryID what = insn->getOperation().getID();
557         if (what != e_ret_near)
558             continue;
559         
560         int val;
561         std::vector<Operand> ops;
562         insn->getOperands(ops);
563         if (ops.size() == 0) {
564             val = 0;
565         }
566         else {      
567             Result imm = ops[0].getValue()->eval();
568             assert(imm.defined);
569             val = (int) imm.val.s16val;
570         }
571         returnCleanVals.insert(Height(val));
572     }
573
574     funcCleanAmounts[func] = meet(returnCleanVals);
575     return funcCleanAmounts[func];
576 }
577
578 StackAnalysis::StackAnalysis() :
579     func(NULL), heightIntervals_(NULL), presenceIntervals_(NULL), 
580     rt(Region::Ptr(new Region())) {};
581     
582
583 StackAnalysis::StackAnalysis(Function *f) : func(f),
584                                             rt(Region::Ptr(new Region())) 
585 {
586     blocks = func->blocks();
587     heightIntervals_ = NULL;
588     presenceIntervals_ = NULL;
589 }
590
591 const StackAnalysis::HeightTree *StackAnalysis::heightIntervals() {
592     if (func == NULL) return NULL;
593
594     // Check the annotation
595     HeightTree *ret;
596     func->getAnnotation(ret, HeightAnno);
597     if (ret) return ret;
598     if (heightIntervals_ == NULL) {
599         if (!analyze()) return NULL;
600         ret = heightIntervals_;
601     }
602
603     return ret;
604 }
605
606
607 const StackAnalysis::PresenceTree *StackAnalysis::presenceIntervals() {
608     if (func == NULL) return NULL;
609
610     // Check the annotation
611     PresenceTree *ret;
612     func->getAnnotation(ret, PresenceAnno);
613     if (ret) return ret;
614
615     if (presenceIntervals_ == NULL) {
616         if (!analyze()) return NULL;
617         ret = presenceIntervals_;
618     }
619
620     return ret;
621 }
622
623 void StackAnalysis::debugHeights() {
624     if (!heightIntervals_) return;
625     std::vector<std::pair<std::pair<Offset, Offset>, Height> > elements;
626     heightIntervals_->elements(elements);
627
628     for (unsigned i = 0; i < elements.size(); i++) {
629         fprintf(stderr, "0x%lx - 0x%lx: %s\n",
630                 elements[i].first.first,
631                 elements[i].first.second,
632                 elements[i].second.format().c_str());
633     }
634 }
635
636 void StackAnalysis::debugPresences() {
637     if (!presenceIntervals_) return;
638
639     std::vector<std::pair<std::pair<Offset, Offset>, Presence> > elements;
640     presenceIntervals_->elements(elements);
641
642     for (unsigned i = 0; i < elements.size(); i++) {
643         fprintf(stderr, "0x%lx - 0x%lx: %s\n",
644                 elements[i].first.first,
645                 elements[i].first.second,
646                 elements[i].second.format().c_str());
647     }
648 }
649
650
651 std::string StackAnalysis::InsnTransferFunc::format() const {
652     char buf[256];
653
654     if (*this == bottom) {
655         sprintf(buf, "<BOTTOM>");
656         return buf;
657     }
658     if (*this == top) {
659         sprintf(buf, "<TOP>");
660         return buf;
661     }
662
663     if (range_ == defaultRange) {
664         if (!abs_) {
665           sprintf(buf, "<%ld>", (long int) delta_);
666         }
667         else {
668           sprintf(buf, "Abs: %ld", (long int) delta_);
669         }
670     }
671     else {
672         sprintf(buf, "%s", range_.format().c_str());
673     }
674     return buf;
675 }
676
677 std::string StackAnalysis::BlockTransferFunc::format() const {
678     if (*this == bottom) {
679         return "<BOTTOM>";
680     }
681     if (*this == top) {
682         return "<TOP>";
683     }
684
685     std::stringstream retVal;
686
687     if (!abs_) {
688         retVal << "<" << delta_ << ">";
689     }
690     else {
691         retVal << "Abs: " << delta_;
692     }
693
694     for (unsigned i = 0; i < ranges_.size(); i++) {
695         retVal << ranges_[i].format();
696     }
697     return retVal.str();
698 }
699
700 void StackAnalysis::InsnTransferFunc::apply(const BlockTransferFunc &in,
701                                             BlockTransferFunc &out) const {
702     out = in;
703
704     apply(out);
705 }
706
707
708 void StackAnalysis::InsnTransferFunc::apply(BlockTransferFunc &out) const {
709     if (out == BlockTransferFunc::bottom) return;
710
711     if (*this == bottom) {
712         out = BlockTransferFunc::bottom;
713         return;
714     }
715
716     if (abs_) {
717         out.delta() = 0;
718         out.abs() = true;
719         out.ranges().clear();
720         out.reset() = true;
721     }
722
723     if (delta_ != uninitialized) {
724         if (out.delta() == uninitialized) {
725             out.delta() = 0;
726         }
727         out.delta() += delta_;
728     }
729
730     if (range_ != defaultRange) {
731         out.ranges().push_back(Range(range_, 
732                                      ((out.delta() == uninitialized ) ? 0 : out.delta())));
733         out.reset() = true;
734         out.delta() = 0;
735     }
736 }
737
738
739 void StackAnalysis::BlockTransferFunc::apply(const BlockTransferFunc &in,
740                                              BlockTransferFunc &out) const {
741     out = in;
742     apply(out);
743 }
744
745 void StackAnalysis::BlockTransferFunc::apply(BlockTransferFunc &out) const {
746     if (out == bottom) return;
747     if (*this == bottom) {
748         out = bottom;
749         return;
750     }
751
752     // abs: we encountered a leave or somesuch
753     // that rebased the stack pointer
754     if (abs_) {
755         // Any increment will happen below.
756         out.delta() = 0;
757         out.ranges().clear();
758         out.abs() = true;
759     }
760
761     // This just says reset delta to 0;
762     // we've got a new relative origin.
763     if (reset_) {
764         out.delta() = 0;
765         out.reset() = true;
766     }
767
768     if (delta_ != uninitialized) {
769         if (out.delta() == uninitialized) {
770             out.delta() = 0;
771         }
772         out.delta() += delta_;
773     }
774     
775     for (unsigned i = 0; i < ranges_.size(); i++) {
776         out.ranges().push_back(ranges_[i]);
777     }
778 }
779
780 void StackAnalysis::Presence::apply(const Presence &in, Presence &out) const {
781     out = in;
782     apply(out);
783 }
784
785 void StackAnalysis::Presence::apply(Presence &out) const {
786     if (presence_ == top_t) return;
787     out.presence_ = presence_;
788 }
789
790 std::string StackAnalysis::Range::format() const {
791     std::stringstream retVal;
792
793     if (off_ == 0) {
794         return "[NONE]";
795     }
796     else {
797         retVal << "[" << std::hex << off_ 
798                << std::dec
799                << ", " << delta_
800                << ", [";
801         if (range_.first == MINLONG)
802             retVal << "-inf";
803         else
804             retVal << range_.first;
805
806         retVal << ",";
807
808         if (range_.second == MAXLONG)
809             retVal << "+inf";
810         else
811             retVal << range_.second;
812         
813         retVal << "]]";
814         return retVal.str();
815     }
816 }
817
818 StackAnalysis::Region::Ptr StackAnalysis::RangeTree::find(Ranges &str) {
819     if (str.empty()) return root->region;
820
821     Node *cur = root;
822     for (unsigned i = 0; i < str.size(); i++) {
823         std::map<Range, Node *>::iterator iter = cur->children.find(str[i]);
824         if (iter == cur->children.end()) {
825             //stackanalysis_printf("\t Creating new node for range %s\n", 
826             //str[i].format().c_str());
827             // Need to create a new node...
828             Node *newNode = new Node(Region::Ptr(new Region(getNewRegionID(),
829                                                             str[i],
830                                                             cur->region)));
831             cur->children[str[i]] = newNode;
832             cur = newNode;
833         }
834         else {
835             //stackanalysis_printf("\t Found existing node for range %s\n",
836             //str[i].format().c_str());
837             cur = iter->second;
838         }
839     }
840     //stackanalysis_printf("\t Returning region %s\n", cur->region->format().c_str());
841     return cur->region;
842 }
843
844 StackAnalysis::Region::Ptr StackAnalysis::getRegion(Ranges &ranges) {
845     return rt.find(ranges);
846 }
847
848 std::string StackAnalysis::Region::format() const {
849     std::stringstream retVal;
850     
851     retVal << "(" << name_ << "," << range_.format() << ") ";
852     if (prev_)
853         retVal << prev_->format();
854
855     return retVal.str();
856 }
857