Improved LEA handling and added mul/div handling.
[dyninst.git] / dataflowAPI / src / stackanalysis.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include "instructionAPI/h/InstructionDecoder.h"
32 #include "instructionAPI/h/Result.h"
33 #include "instructionAPI/h/Instruction.h"
34 #include "instructionAPI/h/BinaryFunction.h"
35 #include "instructionAPI/h/Dereference.h"
36 #include "instructionAPI/h/Expression.h"
37 #include "instructionAPI/h/Immediate.h"
38 #include "instructionAPI/h/Register.h"
39
40 #include <queue>
41 #include <vector>
42 #include <boost/bind.hpp>
43
44 #include "ABI.h"
45 #include "stackanalysis.h"
46
47 #include "Annotatable.h"
48
49 #include "debug_dataflow.h"
50
51 #include "parseAPI/h/CFG.h"
52 #include "parseAPI/h/CodeObject.h"
53
54 using namespace Dyninst;
55 using namespace InstructionAPI;
56 using namespace Dyninst::ParseAPI;
57
58 const StackAnalysis::Height StackAnalysis::Height::bottom(StackAnalysis::Height::notUnique);
59 const StackAnalysis::Height StackAnalysis::Height::top(StackAnalysis::Height::uninitialized);
60
61 AnnotationClass <StackAnalysis::Intervals> Stack_Anno(std::string("Stack_Anno"));
62
63
64 //
65 //
66 // Concepts:
67 //
68 // There are three terms we throw around:
69 // 
70 // Stack height: the size of the stack; (cur_stack_ptr - func_start_stack_ptr)
71 // Stack delta: the difference in the size of the stack over the execution of
72 //   a region of code (basic block here). (block_end_stack_ptr - block_start_stack_ptr)
73 // Stack clean: the amount the callee function shifts the stack. This is an x86 idiom.
74 //   On x86 the caller pushes arguments onto the stack (and thus shifts the stack).
75 //   Normally the caller also cleans the stack (that is, removes arguments). However, 
76 //   some callee functions perform this cleaning themselves. We need to account for this
77 //   in our analysis, which otherwise assumes that callee functions don't alter the stack.
78 // 
79
80 bool StackAnalysis::analyze()
81 {
82
83     df_init_debug();
84
85     stackanalysis_printf("Beginning stack analysis for function %s\n",
86                          func->name().c_str());
87
88     stackanalysis_printf("\tSummarizing block effects\n");
89     summarizeBlocks();
90     
91     stackanalysis_printf("\tPerforming fixpoint analysis\n");
92     fixpoint();
93
94     stackanalysis_printf("\tCreating SP interval tree\n");
95     summarize();
96
97     func->addAnnotation(intervals_, Stack_Anno);
98
99     if (df_debug_stackanalysis) {
100         debug();
101     }
102
103     stackanalysis_printf("Finished stack analysis for function %s\n",
104                          func->name().c_str());
105     return true;
106 }
107
108 // We want to create a transfer function for the block as a whole. 
109 // This will allow us to perform our fixpoint calculation over
110 // blocks (thus, O(B^2)) rather than instructions (thus, O(I^2)). 
111 //
112 // Handling the stack height is straightforward. We also accumulate
113 // region changes in terms of a stack of Region objects.
114
115 typedef std::vector<std::pair<Instruction::Ptr, Offset> > InsnVec;
116
117 static void getInsnInstances(Block *block,
118                              InsnVec &insns) {
119   Offset off = block->start();
120   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
121   if (ptr == NULL) return;
122   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
123   while (off < block->end()) {
124     insns.push_back(std::make_pair(d.decode(), off));
125     off += insns.back().first->size();
126   }
127 }
128
129 void StackAnalysis::summarizeBlocks() {
130   Function::blocklist bs(func->blocks());
131   Function::blocklist::iterator bit = bs.begin();
132   for ( ; bit != bs.end(); ++bit) {
133     Block *block = *bit;
134     // Accumulators. They have the following behavior:
135     // 
136     // New region: add to the end of the regions list
137     // Offset to stack pointer: accumulate to delta.
138     // Setting the stack pointer: zero delta, set set_value.
139     // 
140
141     SummaryFunc &bFunc = blockEffects[block];
142
143     stackanalysis_printf("\t Block starting at 0x%lx: %s\n", 
144                          block->start(),
145                          bFunc.format().c_str());
146     InsnVec instances;
147     getInsnInstances(block, instances);
148
149     for (unsigned j = 0; j < instances.size(); j++) {
150       InstructionAPI::Instruction::Ptr insn = instances[j].first;
151       Offset &off = instances[j].second;
152
153       // Fills in insnEffects[off]
154       TransferFuncs &xferFuncs = insnEffects[block][off];
155
156       computeInsnEffects(block, insn, off, xferFuncs);
157       bFunc.add(xferFuncs);
158
159       stackanalysis_printf("\t\t\t At 0x%lx:  %s\n", off,
160         bFunc.format().c_str());
161     }
162     stackanalysis_printf("\t Block summary for 0x%lx: %s\n", block->start(),
163       bFunc.format().c_str());
164   }
165 }
166
167 struct intra_nosink : public ParseAPI::EdgePredicate
168 {
169   virtual bool operator()(Edge* e)
170   {
171     static Intraproc i;
172     static NoSinkPredicate n;
173     
174     return i(e) && n(e);
175   }
176   
177 };
178
179 void add_target(std::queue<Block*>& worklist, Edge* e)
180 {
181    worklist.push(e->trg());
182 }
183
184 void StackAnalysis::fixpoint() {
185    std::queue<Block *> worklist;
186
187    //Intraproc epred; // ignore calls, returns in edge iteration
188    //NoSinkPredicate nosink(); // ignore sink node (unresolvable)
189    intra_nosink epred2;
190
191    worklist.push(func->entry());
192
193    Block *entry = func->entry();
194
195    while (!worklist.empty()) {
196       Block *block = worklist.front();
197       stackanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n",
198          block->start());
199
200       worklist.pop();
201
202       // Step 1: calculate the meet over the heights of all incoming
203       // intraprocedural blocks.
204
205       AbslocState input;
206
207       if (block == entry) {
208          createEntryInput(input);
209          stackanalysis_printf("\t Primed initial block\n");
210       }
211       else {
212          stackanalysis_printf("\t Calculating meet with block [%x-%x]\n",
213             block->start(), block->lastInsnAddr());
214          meetInputs(block, blockInputs[block], input);
215       }
216
217       stackanalysis_printf("\t New in meet: %s\n", format(input).c_str());
218
219       // Step 2: see if the input has changed
220
221       if (input == blockInputs[block]) {
222          // No new work here
223          stackanalysis_printf("\t ... equal to current, skipping block\n");
224          continue;
225       }
226
227       stackanalysis_printf("\t ... inequal to current %s, analyzing block\n",
228          format(blockInputs[block]).c_str());
229
230       blockInputs[block] = input;
231
232       // Step 3: calculate our new outs
233
234       blockEffects[block].apply(input, blockOutputs[block]);
235
236       stackanalysis_printf("\t ... output from block: %s\n",
237          format(blockOutputs[block]).c_str());
238
239       // Step 4: push all children on the worklist.
240
241       const Block::edgelist & outEdges = block->targets();
242       std::for_each(
243          boost::make_filter_iterator(epred2, outEdges.begin(), outEdges.end()),
244          boost::make_filter_iterator(epred2, outEdges.end(), outEdges.end()),
245          boost::bind(add_target, boost::ref(worklist), _1)
246       );
247    }
248 }
249
250
251
252 void StackAnalysis::summarize() {
253     // Now that we know the actual inputs to each block,
254     // we create intervals by replaying the effects of each
255     // instruction.
256
257     intervals_ = new Intervals();
258
259     Function::blocklist bs = func->blocks();
260     Function::blocklist::iterator bit = bs.begin();
261     for ( ; bit != bs.end(); ++bit) {
262         Block *block = *bit;
263         AbslocState input = blockInputs[block];
264
265         std::map<Offset, TransferFuncs>::iterator iter;
266         for (iter = insnEffects[block].begin();
267             iter != insnEffects[block].end(); ++iter) {
268             Offset off = iter->first;
269             TransferFuncs &xferFuncs = iter->second;
270
271             // TODO: try to collapse these in some intelligent fashion
272             (*intervals_)[block][off] = input;
273
274             for (TransferFuncs::iterator iter2 = xferFuncs.begin();
275                 iter2 != xferFuncs.end(); ++iter2) {
276                 input[iter2->target] = iter2->apply(input);
277             }
278         }
279         (*intervals_)[block][block->end()] = input;
280         assert(input == blockOutputs[block]);
281     }
282 }
283
284 void StackAnalysis::computeInsnEffects(ParseAPI::Block *block,
285                                        Instruction::Ptr insn,
286                                        const Offset off,
287                                        TransferFuncs &xferFuncs) {
288     stackanalysis_printf("\t\tInsn at 0x%lx\n", off);
289     entryID what = insn->getOperation().getID();
290
291     // Reminder: what we're interested in:
292     // a) Use of the stack pointer to define another register
293     //      Assumption: this is done by an e_mov and is a direct copy
294     //                  else bottom
295     // b) Use of another register to define the stack pointer
296     //      Assumption: see ^^
297     // c) Modification of the stack pointer
298     // 
299     // The reason for these assumptions is to keep the analysis reasonable; also,
300     // other forms just don't occur. 
301     //
302     // In summary, the stack pointer must be read or written for us to be interested.
303     // 
304     // However, we need to detect when a register is destroyed. So if something is written,
305     // we assume it is destroyed.
306     // 
307     // For now, we assume an all-to-all mapping for speed. 
308
309     // Cases we handle
310     if (isCall(insn)) {
311        if (handleNormalCall(insn, block, off, xferFuncs))
312           return;
313        else if (handleThunkCall(insn, xferFuncs))
314           return;
315        else
316           return handleDefault(insn, xferFuncs);
317     }
318
319     int sign = 1;
320     switch (what) {
321        case e_push:
322           sign = -1;
323           //FALLTHROUGH
324        case e_pop:
325           handlePushPop(insn, sign, xferFuncs);
326           break;
327        case e_ret_near:
328        case e_ret_far:
329           handleReturn(insn, xferFuncs);
330           break;
331        case e_lea:
332           handleLEA(insn, xferFuncs);
333           break;
334        case e_sub:
335           sign = -1;
336           //FALLTHROUGH
337        case e_add:
338           handleAddSub(insn, sign, xferFuncs);
339           break;
340        case e_leave:
341           handleLeave(xferFuncs);
342           break;
343        case e_pushfd:
344           sign = -1;
345           //FALLTHROUGH
346        case e_popfd:
347           handlePushPopFlags(sign, xferFuncs);
348           break;
349        case e_pushad:
350           sign = -1;
351           handlePushPopRegs(sign, xferFuncs);
352           break;
353        case e_popad:
354           // This nukes all registers
355           handleDefault(insn, xferFuncs);
356           break;
357        case power_op_addi:
358        case power_op_addic:
359           handlePowerAddSub(insn, sign, xferFuncs);
360           break;
361        case power_op_stwu:
362           handlePowerStoreUpdate(insn, xferFuncs);
363           break;
364        case e_mov:
365           handleMov(insn, off, xferFuncs);
366           break;
367        case e_movzx:
368           handleZeroExtend(insn, xferFuncs);
369           break;
370        case e_movsx:
371        case e_movsxd:
372        case e_cbw:
373        case e_cwde:
374           handleSignExtend(insn, xferFuncs);
375           break;
376        case e_xor:
377           handleXor(insn, xferFuncs);
378           break;
379        case e_div:
380        case e_idiv:
381           handleDiv(insn, xferFuncs);
382           break;
383        case e_mul:
384        case e_imul:
385           handleMul(insn, xferFuncs);
386           break;
387        default:
388           handleDefault(insn, xferFuncs);
389     }
390 }
391
392 StackAnalysis::Height StackAnalysis::getStackCleanAmount(Function *func) {
393     // Cache previous work...
394     if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
395         return funcCleanAmounts[func];
396     }
397
398     if (!func->cleansOwnStack()) {
399         funcCleanAmounts[func] = 0;
400         return funcCleanAmounts[func];
401     }
402
403     InstructionDecoder decoder((const unsigned char*)NULL, 0, func->isrc()->getArch());
404     unsigned char *cur;
405
406     std::set<Height> returnCleanVals;
407
408     Function::const_blocklist returnBlocks = func->returnBlocks();
409     auto rets = returnBlocks.begin();
410     for (; rets != returnBlocks.end(); ++rets) {
411          Block *ret = *rets;
412          cur = (unsigned char *) ret->region()->getPtrToInstruction(ret->lastInsnAddr());
413          Instruction::Ptr insn = decoder.decode(cur);
414
415          entryID what = insn->getOperation().getID();
416          if (what != e_ret_near)
417              continue;
418       
419          int val;
420          std::vector<Operand> ops;
421          insn->getOperands(ops);
422          if (ops.size() == 1) {
423              val = 0;
424          } else {
425              Result imm = ops[1].getValue()->eval();
426              assert(imm.defined);
427              val = (int) imm.val.s16val;
428          }
429          returnCleanVals.insert(Height(val));
430     }
431
432         Height clean = Height::meet(returnCleanVals);
433         if (clean == Height::top) {
434                 // Non-returning or tail-call exits?
435                 clean = Height::bottom;
436         }
437
438     funcCleanAmounts[func] = clean;
439
440     return clean;
441 }
442
443 StackAnalysis::StackAnalysis() :
444    func(NULL), intervals_(NULL), word_size(0) {};
445    
446
447 StackAnalysis::StackAnalysis(Function *f) : func(f),
448                                             intervals_(NULL) {
449    word_size = func->isrc()->getAddressWidth();
450    theStackPtr = Expression::Ptr(new RegisterAST(MachRegister::getStackPointer(func->isrc()->getArch())));
451    thePC = Expression::Ptr(new RegisterAST(MachRegister::getPC(func->isrc()->getArch())));
452 };
453
454 void StackAnalysis::debug() {
455 }
456
457 std::string StackAnalysis::TransferFunc::format() const {
458    std::stringstream ret;
459
460    ret << "[";
461    if (target.isValid())
462       ret << target.format();
463    else
464       ret << "<INVALID>";
465    ret << ":=";
466    if (isBottom()) ret << "<BOTTOM>";
467    else if (isRetop()) ret << "<re-TOP>";
468    else if (isTop()) ret << "<TOP>";
469    else {
470       bool foundType = false;
471       if (isAlias()) {
472          ret << from.format();
473          foundType = true;
474       }
475       if (isAbs()) {
476          ret << abs << dec;
477          foundType = true;
478       }
479       if (isSIB()) {
480           for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
481               if (iter != fromRegs.begin()) {
482                   ret << "+";
483               }
484               ret << "(";
485               ret << (*iter).first.format() << "*" << (*iter).second.first;
486               if ((*iter).second.second) {
487                   ret << ", will round to TOP or BOTTOM";
488               }
489               ret << ")";
490           }
491           foundType = true;
492       }
493       if (isDelta()) {
494           if (!foundType) {
495             ret << target.format() << "+" << delta;
496           } else {
497             ret << "+" << delta;
498           }
499       }
500    }
501    if (isTopBottom()) {
502     ret << ", will round to TOP or BOTTOM";
503    }
504    ret << "]";
505    return ret.str();
506 }
507
508 std::string StackAnalysis::SummaryFunc::format() const {
509    stringstream ret;
510    for (TransferSet::const_iterator iter = accumFuncs.begin();
511         iter != accumFuncs.end(); ++iter) {
512       ret << iter->second.format() << endl;
513    }
514    return ret.str();
515 }
516
517
518 void StackAnalysis::findDefinedHeights(ParseAPI::Block* b, Address addr, std::vector<std::pair<Absloc, Height> >& heights)
519 {
520   if (func == NULL) return;
521
522   if (!intervals_) {
523     // Check annotation
524     func->getAnnotation(intervals_, Stack_Anno);
525   }
526   if (!intervals_) {
527     // Analyze?
528     if (!analyze()) return;
529   }
530   assert(intervals_);
531   for(AbslocState::iterator i = (*intervals_)[b][addr].begin();
532       i != (*intervals_)[b][addr].end();
533       ++i)
534   {
535     if(i->second.isTop())
536     {
537       continue;
538     }
539     stackanalysis_printf("\t\tAdding %s:%s to defined heights at 0x%lx\n",
540                          i->first.format().c_str(),
541                          i->second.format().c_str(),
542                          addr);
543
544     heights.push_back(*i);
545   }
546 }
547
548 StackAnalysis::Height StackAnalysis::find(Block *b, Address addr, Absloc loc) {
549
550   Height ret; // Defaults to "top"
551
552   if (func == NULL) return ret;
553   
554   if (!intervals_) {
555     // Check annotation
556     func->getAnnotation(intervals_, Stack_Anno);
557   }
558   if (!intervals_) {
559     // Analyze?
560     if (!analyze()) return Height();
561   }
562   assert(intervals_);
563
564   //(*intervals_)[b].find(addr, state);
565   //  ret = (*intervals_)[b][addr][reg];
566   Intervals::iterator iter = intervals_->find(b);
567   if (iter == intervals_->end()) {
568           // How do we return "you stupid idiot"?
569
570           return Height::bottom;
571   }
572
573   StateIntervals &sintervals = iter->second;
574   if (sintervals.empty()) {
575           return Height::bottom;
576   }
577   //Find the last instruction that is <= addr
578   StateIntervals::iterator i = sintervals.lower_bound(addr);
579   if ((i == sintervals.end() && !sintervals.empty()) || 
580       (i->first != addr && i != sintervals.begin())) {
581       i--;
582   }
583   if (i == sintervals.end()) return Height::bottom;
584
585   ret = i->second[loc];
586
587   if (ret.isTop()) {
588      return Height::bottom;
589   }
590   return ret;
591 }
592
593 StackAnalysis::Height StackAnalysis::findSP(Block *b, Address addr) {
594    return find(b, addr, Absloc(sp()));
595 }
596
597 StackAnalysis::Height StackAnalysis::findFP(Block *b, Address addr) {
598    return find(b, addr, Absloc(fp()));
599 }
600
601 std::ostream &operator<<(std::ostream &os, const Dyninst::StackAnalysis::Height &h) {
602   os << "STACK_SLOT[" << h.format() << "]";
603   return os;
604 }
605
606 ///////////////////
607 // Insn effect fragments
608 ///////////////////
609 void StackAnalysis::handleXor(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
610    std::vector<Operand> operands;
611    insn->getOperands(operands);
612    assert(operands.size() == 2);
613
614    // Handle the case where a register is being zeroed out.
615    // We recognize such cases as follows:
616    //   1. Exactly one register is both read and written
617    //   2. The Expression tree for each operand consists of a single leaf node
618    std::set<RegisterAST::Ptr> readSet;
619    std::set<RegisterAST::Ptr> writtenSet;
620    operands[0].getWriteSet(writtenSet);
621    operands[1].getReadSet(readSet);
622
623    std::vector<Expression::Ptr> children0;
624    std::vector<Expression::Ptr> children1;
625    operands[0].getValue()->getChildren(children0);
626    operands[1].getValue()->getChildren(children1);
627
628    if (readSet.size() == 1 && writtenSet.size() == 1 &&
629       (*readSet.begin())->getID() == (*writtenSet.begin())->getID() &&
630       children0.size() == 0 && children1.size() == 0) {
631       stackanalysis_printf("\t\t\t Register zeroing detected\n");
632       Absloc loc((*writtenSet.begin())->getID());
633       xferFuncs.push_back(TransferFunc::absFunc(loc, 0));
634    } else {
635       handleDefault(insn, xferFuncs);
636    }
637 }
638
639
640 void StackAnalysis::handleDiv(Instruction::Ptr insn,
641    TransferFuncs &xferFuncs) {
642    stackanalysis_printf("\t\t\thandleDiv: %s\n", insn->format().c_str());
643    std::vector<Operand> operands;
644    insn->getOperands(operands);
645    assert(operands.size() == 3);
646
647    Expression::Ptr quotient = operands[1].getValue();
648    Expression::Ptr remainder = operands[0].getValue();
649    Expression::Ptr divisor = operands[2].getValue();
650    assert(typeid(*quotient) == typeid(RegisterAST));
651    assert(typeid(*remainder) == typeid(RegisterAST));
652    assert(typeid(*divisor) != typeid(Immediate));
653
654    MachRegister quotientReg = (boost::dynamic_pointer_cast<InstructionAPI::
655       RegisterAST>(quotient))->getID();
656    MachRegister remainderReg = (boost::dynamic_pointer_cast<InstructionAPI::
657       RegisterAST>(remainder))->getID();
658
659    xferFuncs.push_back(TransferFunc::retopFunc(Absloc(quotientReg)));
660    xferFuncs.push_back(TransferFunc::retopFunc(Absloc(remainderReg)));
661 }
662
663
664 void StackAnalysis::handleMul(Instruction::Ptr insn,
665    TransferFuncs &xferFuncs) {
666    // MULs have a few forms:
667    //   1. mul reg1, reg2/mem2
668    //     -- reg1 = reg1 * reg2/mem2
669    //   2. mul reg1, reg2/mem2, imm3
670    //     -- reg1 = reg2/mem2 * imm3
671    //   3. mul reg1, reg2, reg3/mem3
672    //     -- reg1:reg2 = reg2 * reg3/mem3
673    stackanalysis_printf("\t\t\thandleMul: %s\n", insn->format().c_str());
674    std::vector<Operand> operands;
675    insn->getOperands(operands);
676    assert(operands.size() == 2 || operands.size() == 3);
677
678    Expression::Ptr target = operands[0].getValue();
679    assert(typeid(*target) == typeid(RegisterAST));
680    MachRegister targetReg = (boost::dynamic_pointer_cast<InstructionAPI::
681       RegisterAST>(target))->getID();
682
683    if (operands.size() == 2) {
684       // Form 1
685       xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
686    } else {
687       Expression::Ptr multiplicand = operands[1].getValue();
688       Expression::Ptr multiplier = operands[2].getValue();
689
690       if (typeid(*multiplier) == typeid(Immediate)) {
691          // Form 2
692          assert(typeid(*multiplicand) == typeid(RegisterAST) ||
693             typeid(*multiplicand) == typeid(Dereference));
694          long multiplierVal = multiplier->eval().convert<long>();
695          if (multiplierVal == 0) {
696             xferFuncs.push_back(TransferFunc::absFunc(Absloc(targetReg), 0));
697          } else if (multiplierVal == 1) {
698             if (typeid(*multiplicand) == typeid(RegisterAST)) {
699                // mul reg1, reg2, 1
700                MachRegister multiplicandReg = boost::dynamic_pointer_cast<
701                   RegisterAST>(multiplicand)->getID();
702                Absloc targetLoc(targetReg);
703                Absloc multiplicandLoc(multiplicandReg);
704                xferFuncs.push_back(TransferFunc::aliasFunc(multiplicandLoc,
705                   targetLoc));
706             } else {
707                // mul reg1, mem2, 1
708                Absloc targetLoc(targetReg);
709                xferFuncs.push_back(TransferFunc::bottomFunc(targetLoc));
710             }
711          } else {
712             xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
713          }
714       } else {
715          // Form 3
716          assert(typeid(*multiplicand) == typeid(RegisterAST));
717          assert(typeid(*multiplier) == typeid(RegisterAST) ||
718             typeid(*multiplier) == typeid(Dereference));
719          MachRegister multiplicandReg = boost::dynamic_pointer_cast<
720             RegisterAST>(multiplicand)->getID();
721          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
722          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(multiplicandReg)));
723       }
724    }
725 }
726
727
728 void StackAnalysis::handlePushPop(Instruction::Ptr insn, int sign,
729    TransferFuncs &xferFuncs) {
730
731    long delta = 0;
732    Operand arg = insn->getOperand(0);
733    // Why was this here? bernat, 12JAN11
734    if (arg.getValue()->eval().defined) {
735       delta = sign * word_size;
736       stackanalysis_printf(
737          "\t\t\t Stack height changed by evaluated push/pop: %lx\n", delta);
738    }
739    else {
740       delta = sign * arg.getValue()->size();
741       //cerr << "Odd case: set delta to " << hex << delta << dec << " for instruction " << insn->format() << endl;
742       stackanalysis_printf(
743          "\t\t\t Stack height changed by unevalled push/pop: %lx\n", delta);
744    }
745    //   delta = sign *arg.getValue()->size();
746    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
747
748    // Let's get whatever was popped (if it was)
749    if (insn->getOperation().getID() == e_pop &&
750        !insn->writesMemory()) {
751       MachRegister reg = sp();
752
753       std::set<RegisterAST::Ptr> written;
754       insn->getWriteSet(written);
755       for (std::set<RegisterAST::Ptr>::iterator iter = written.begin(); 
756            iter != written.end(); ++iter) {
757          if ((*iter)->getID() != sp()) reg = (*iter)->getID();
758       }
759       xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(reg)));
760    }
761 }
762
763 void StackAnalysis::handleReturn(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
764    long delta = 0;
765    std::vector<Operand> operands;
766    insn->getOperands(operands);
767    if (operands.size() == 0) {
768       delta = word_size;
769    }
770    else if (operands.size() == 1) {
771       // Ret immediate
772       Result imm = operands[0].getValue()->eval();
773       if (imm.defined) {
774          delta = word_size + imm.convert<int>();
775       }
776       else {
777          stackanalysis_printf("\t\t\t Stack height changed by return: bottom\n");
778          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(sp())));
779       }
780    }
781    stackanalysis_printf("\t\t\t Stack height changed by return: %lx\n", delta);
782    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
783 }
784
785 void StackAnalysis::handleAddSub(Instruction::Ptr insn, int sign, TransferFuncs &xferFuncs) {
786    // add reg, mem is ignored
787    // add mem, reg bottoms reg
788    if (insn->writesMemory()) return;
789    if (insn->readsMemory()) {
790       handleDefault(insn, xferFuncs);
791       return;
792    }
793
794    std::set<RegisterAST::Ptr> readSet;
795    insn->getOperand(0).getReadSet(readSet);
796    if (readSet.size() != 1) {
797       fprintf(stderr, "readSet != 1\n");
798       handleDefault(insn, xferFuncs);
799       return;
800    }
801
802    // Add/subtract are op0 += (or -=) op1
803    Operand arg = insn->getOperand(1);
804    Result res = arg.getValue()->eval();
805    if (res.defined) {
806       long delta = sign * extractDelta(res);
807       stackanalysis_printf(
808          "\t\t\t Stack height changed by evalled add/sub: %lx\n", delta);
809       Absloc loc((*(readSet.begin()))->getID());
810       xferFuncs.push_back(TransferFunc::deltaFunc(loc, delta));
811    }
812    else {
813       handleDefault(insn, xferFuncs);
814    }
815
816    return;
817 }
818
819 void StackAnalysis::handleLEA(Instruction::Ptr insn,
820    TransferFuncs &xferFuncs) {
821    // LEA has a few patterns:
822    //   op0: target register
823    //-------------------------------
824    //   op1: reg + reg * imm + imm
825    //            or
826    //   op1: reg + reg * imm
827    //            or
828    //   op1: imm + reg * imm
829    //            or
830    //   op1: reg + imm
831    //            or
832    //   op1: reg
833    //
834
835    stackanalysis_printf("\t\t\t handleLEA, insn = %s\n",
836       insn->format().c_str());
837
838    std::set<RegisterAST::Ptr> readSet;
839    std::set<RegisterAST::Ptr> writtenSet;
840    insn->getOperand(0).getWriteSet(writtenSet);
841    insn->getOperand(1).getReadSet(readSet);
842    assert(writtenSet.size() == 1);
843    assert(readSet.size() == 1 || readSet.size() == 2);
844    MachRegister written = (*writtenSet.begin())->getID();
845    Absloc writeloc(written);
846
847    InstructionAPI::Operand srcOperand = insn->getOperand(1);
848    InstructionAPI::Expression::Ptr srcExpr = srcOperand.getValue();
849    std::vector<InstructionAPI::Expression::Ptr> children;
850    srcExpr->getChildren(children);
851
852    stackanalysis_printf("\t\t\t\t srcOperand = %s\n",
853       srcExpr->format().c_str());
854
855    if (readSet.size() == 1) {
856       InstructionAPI::Expression::Ptr regExpr, scaleExpr, deltaExpr;
857       bool foundScale = false;
858       bool foundDelta = false;
859
860       if (children.size() == 2) {
861          if (typeid(*children[0]) == typeid(Immediate)) {
862             // op1: imm + reg * imm
863             deltaExpr = children[0];
864             Expression::Ptr scaleIndexExpr = children[1];
865             assert(typeid(*scaleIndexExpr) == typeid(BinaryFunction));
866             children.clear();
867             scaleIndexExpr->getChildren(children);
868
869             regExpr = children[0];
870             scaleExpr = children[1];
871             assert(typeid(*regExpr) == typeid(RegisterAST));
872             assert(typeid(*scaleExpr) == typeid(Immediate));
873             foundScale = true;
874             foundDelta = true;
875          } else if (typeid(*children[0]) == typeid(RegisterAST)) {
876             // op1: reg + imm
877             regExpr = children[0];
878             deltaExpr = children[1];
879             stackanalysis_printf("\t\t\t\t reg: %s\n",
880                regExpr->format().c_str());
881             stackanalysis_printf("\t\t\t\t delta: %s\n",
882                deltaExpr->format().c_str());
883             assert(typeid(*regExpr) == typeid(RegisterAST));
884             assert(typeid(*deltaExpr) == typeid(Immediate));
885             foundDelta = true;
886          } else {
887             assert(false);
888          }
889       } else if (children.size() == 0) {
890          // op1: reg
891          regExpr = srcExpr;
892          assert(typeid(*regExpr) == typeid(RegisterAST));
893       } else {
894          assert(false);
895       }
896
897       MachRegister reg = (boost::dynamic_pointer_cast<InstructionAPI::
898          RegisterAST>(regExpr))->getID();
899
900       long scale = 1;
901       if (foundScale) {
902          scale = scaleExpr->eval().convert<long>();
903       }
904
905       long delta = 0;
906       if (foundDelta) {
907          delta = extractDelta(deltaExpr->eval());
908       }
909
910       if (foundScale) {
911          std::map<Absloc,std::pair<long, bool> > fromRegs;
912          fromRegs.insert(make_pair(Absloc(reg), make_pair(scale, false)));
913          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, delta, writeloc));
914       } else {
915          Absloc readloc(reg);
916          TransferFunc lea = TransferFunc::aliasFunc(readloc, writeloc);
917          lea.delta = delta;
918          xferFuncs.push_back(lea);
919       }
920    } else if (readSet.size() == 2) {
921       Expression::Ptr baseExpr, indexExpr, scaleExpr, deltaExpr;
922       bool foundDelta = false;
923
924       assert(children.size() == 2);
925       if (typeid(*children[1]) == typeid(Immediate)) {
926          // op1: reg + reg * imm + imm
927          // Extract the delta and continue on to get base, index, and scale
928          deltaExpr = children[1];
929          stackanalysis_printf("\t\t\t\t delta: %s\n",
930             deltaExpr->format().c_str());
931          Expression::Ptr sibExpr = children[0];
932          assert(typeid(*sibExpr) == typeid(BinaryFunction));
933          children.clear();
934          sibExpr->getChildren(children);
935          assert(children.size() == 2);
936          foundDelta = true;
937       }
938
939       // op1: reg + reg * imm
940       baseExpr = children[0];
941       Expression::Ptr scaleIndexExpr = children[1];
942       stackanalysis_printf("\t\t\t\t base: %s\n", baseExpr->format().c_str());
943       assert(typeid(*scaleIndexExpr) == typeid(BinaryFunction));
944
945       // Extract the index and scale
946       children.clear();
947       scaleIndexExpr->getChildren(children);
948       assert(children.size() == 2);
949       indexExpr = children[0];
950       scaleExpr = children[1];
951       stackanalysis_printf("\t\t\t\t index: %s\n",
952          indexExpr->format().c_str());
953       stackanalysis_printf("\t\t\t\t scale: %s\n",
954          scaleExpr->format().c_str());
955
956       assert(typeid(*baseExpr) == typeid(RegisterAST));
957       assert(typeid(*indexExpr) == typeid(RegisterAST));
958       assert(typeid(*scaleExpr) == typeid(Immediate));
959
960       MachRegister base = (boost::dynamic_pointer_cast<InstructionAPI::
961          RegisterAST>(baseExpr))->getID();
962       MachRegister index = (boost::dynamic_pointer_cast<InstructionAPI::
963          RegisterAST>(indexExpr))->getID();
964       long scale = scaleExpr->eval().convert<long>();
965
966       long delta = 0;
967       if (foundDelta) {
968          Result deltaRes = deltaExpr->eval();
969          delta = extractDelta(deltaRes);
970       }
971
972       assert(base.isValid() && index.isValid() && scale != -1);
973
974       // Consolidate when possible
975       if (base == index) {
976          base = MachRegister();
977          scale++;
978       }
979
980       std::map<Absloc,std::pair<long,bool> > fromRegs;
981       if (base.isValid()) {
982          fromRegs.insert(make_pair(Absloc(base), make_pair(1, false)));
983       }
984       fromRegs.insert(make_pair(Absloc(index), make_pair(scale, false)));
985       xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, delta, writeloc));
986    } else {
987       assert(false);
988    }
989 }
990
991 void StackAnalysis::handleLeave(TransferFuncs &xferFuncs) {
992    // This is... mov esp, ebp; pop ebp.
993    // Handle it as such.
994
995    // mov esp, ebp;
996    xferFuncs.push_back(TransferFunc::aliasFunc(Absloc(fp()), Absloc(sp())));
997
998    // pop ebp
999    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), word_size));
1000    xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(fp())));
1001 }
1002
1003 void StackAnalysis::handlePushPopFlags(int sign, TransferFuncs &xferFuncs) {
1004    // Fixed-size push/pop
1005    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), sign * word_size));
1006 }
1007
1008 void StackAnalysis::handlePushPopRegs(int sign, TransferFuncs &xferFuncs) {
1009    // Fixed-size push/pop
1010    // 8 registers
1011    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), sign * 8 * word_size));
1012 }
1013
1014 void StackAnalysis::handlePowerAddSub(Instruction::Ptr insn, int sign,
1015    TransferFuncs &xferFuncs) {
1016
1017    // Add/subtract are op0 = op1 +/- op2; we'd better read the stack pointer as well as writing it
1018    if (!insn->isRead(theStackPtr) ||
1019        !insn->isWritten(theStackPtr)) {
1020       return handleDefault(insn, xferFuncs);
1021    }
1022    
1023    Operand arg = insn->getOperand(2);
1024    Result res = arg.getValue()->eval();
1025    Absloc sploc(sp());
1026    if (res.defined) {
1027       xferFuncs.push_back(TransferFunc::deltaFunc(sploc,
1028          sign * res.convert<long>()));
1029       stackanalysis_printf(
1030          "\t\t\t Stack height changed by evalled add/sub: %lx\n",
1031          sign * res.convert<long>());
1032    }
1033    else {
1034       xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1035       stackanalysis_printf(
1036          "\t\t\t Stack height changed by unevalled add/sub: bottom\n");
1037    }
1038    return;
1039 }
1040
1041 void StackAnalysis::handlePowerStoreUpdate(Instruction::Ptr insn,
1042    TransferFuncs &xferFuncs) {
1043
1044    if(!insn->isWritten(theStackPtr)) {
1045       return handleDefault(insn, xferFuncs);
1046    }
1047    
1048    std::set<Expression::Ptr> memWriteAddrs;
1049    insn->getMemoryWriteOperands(memWriteAddrs);
1050    Expression::Ptr stackWrite = *(memWriteAddrs.begin());
1051    stackanalysis_printf("\t\t\t ...checking operand %s\n",
1052       stackWrite->format().c_str());
1053    stackanalysis_printf("\t\t\t ...binding %s to 0\n",
1054       theStackPtr->format().c_str());
1055    stackWrite->bind(theStackPtr.get(), Result(u32, 0));
1056    Result res = stackWrite->eval();
1057    Absloc sploc(sp());
1058    if (res.defined) {
1059       long delta = res.convert<long>();
1060       xferFuncs.push_back(TransferFunc::deltaFunc(sploc, delta));
1061       stackanalysis_printf(
1062          "\t\t\t Stack height changed by evalled stwu: %lx\n", delta);
1063    }
1064    else {
1065       xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1066       stackanalysis_printf(
1067          "\t\t\t Stack height changed by unevalled stwu: bottom\n");
1068    }
1069 }
1070
1071 // Visitor class to evaluate addresses relative to %rip
1072 class PCRelativeVisitor : public Visitor {
1073 private:
1074    Address rip;
1075    std::deque<Address> results;
1076    bool defined;
1077
1078 public:
1079    // addr is the starting address of instruction insn.
1080    // insn is the instruction containing the expression to evaluate.
1081    PCRelativeVisitor(Address addr, Instruction::Ptr insn) : defined(true) {
1082       rip = addr + insn->size();
1083    }
1084
1085    bool isDefined() {
1086       return defined && results.size() == 1;
1087    }
1088
1089    Address getResult() {
1090       return isDefined() ? results.back() : 0;
1091    }
1092
1093    virtual void visit(BinaryFunction *bf) {
1094       if (!defined) return;
1095
1096       Address arg1 = results.back();
1097       results.pop_back();
1098       Address arg2 = results.back();
1099       results.pop_back();
1100
1101       if (bf->isAdd()) {
1102          results.push_back(arg1 + arg2);
1103       } else if (bf->isMultiply()) {
1104          results.push_back(arg1 * arg2);
1105       } else {
1106          defined = false;
1107       }
1108    }
1109
1110    virtual void visit(Immediate *imm) {
1111       if (!defined) return;
1112
1113       results.push_back(imm->eval().convert<Address>());
1114    }
1115
1116    virtual void visit(RegisterAST *rast) {
1117       if (!defined) return;
1118
1119       MachRegister reg = rast->getID();
1120       if (reg == x86::eip || reg == x86_64::eip || reg == x86_64::rip) {
1121          results.push_back(rip);
1122       } else {
1123          defined = false;
1124       }
1125    }
1126
1127    virtual void visit(Dereference *) {
1128       defined = false;
1129    }
1130 };
1131
1132 void StackAnalysis::handleMov(Instruction::Ptr insn, const Offset off,
1133    TransferFuncs &xferFuncs) {
1134    // Some cases:
1135    //   1. mov reg, reg
1136    //   2. mov imm, reg
1137    //   3. mov mem, reg
1138    //   4. mov reg, mem
1139    //   5. mov imm, mem
1140    // 
1141    // #1 Causes register aliasing.
1142    // #2 Causes an absolute value in the register.
1143    // #3 Depends on whether the memory address we're loading from can be
1144    //    determined statically.
1145    //    a. If it can, we alias the register to the memory location we're
1146    //       loading from.
1147    //    b. Otherwise, we set the register to BOTTOM.
1148    // #4 Depends on whether the address we're storing to can be determined
1149    //    statically.
1150    //    a. If it can, we alias the memory address to the register.
1151    //    b. Otherwise, we ignore the store.
1152    // #5 Depends on whether the address we're storing to can be determined
1153    //    statically.
1154    //    a. If it can, we give the address an absolute value.
1155    //    b. Otherwise, we ignore the store.
1156
1157    Architecture arch = insn->getArch();  // Needed for debug messages
1158
1159    // Extract operands
1160    std::vector<Operand> operands;
1161    insn->getOperands(operands);
1162    assert(operands.size() == 2);
1163
1164    // Extract written/read register sets
1165    std::set<RegisterAST::Ptr> writtenRegs;
1166    std::set<RegisterAST::Ptr> readRegs;
1167    operands[0].getWriteSet(writtenRegs);
1168    operands[1].getReadSet(readRegs);
1169
1170
1171    if (insn->writesMemory()) {
1172       assert(writtenRegs.size() == 0);
1173       stackanalysis_printf("\t\t\tMemory write to: %s\n",
1174          operands[0].format(arch).c_str());
1175
1176       // Extract the expression inside the dereference
1177       std::vector<Expression::Ptr> addrExpr;
1178       operands[0].getValue()->getChildren(addrExpr);
1179       assert(addrExpr.size() == 1);
1180
1181       // Try to determine the written memory address
1182       Address writtenAddr;
1183       PCRelativeVisitor visitor(off, insn);
1184       addrExpr[0]->apply(&visitor);
1185       if (visitor.isDefined()) {
1186          writtenAddr = visitor.getResult();
1187          stackanalysis_printf("\t\t\tSimplifies to: %lx\n", writtenAddr);
1188       } else {
1189          // Cases 4b and 5b
1190          stackanalysis_printf("\t\t\tCan't determine statically\n");
1191          return;
1192       }
1193
1194       if (readRegs.size() > 0) {
1195          // Case 4a
1196          assert(readRegs.size() == 1);
1197          Absloc from((*readRegs.begin())->getID());
1198          Absloc to(writtenAddr);
1199          xferFuncs.push_back(TransferFunc::aliasFunc(from, to));
1200       } else {
1201          // Case 5a
1202          Expression::Ptr immExpr = operands[1].getValue();
1203          assert(typeid(*immExpr) == typeid(Immediate));
1204          long immVal = immExpr->eval().convert<long>();
1205          Absloc to(writtenAddr);
1206          xferFuncs.push_back(TransferFunc::absFunc(to, immVal));
1207       }
1208       return;
1209    }
1210
1211
1212    // Only Cases 1, 2, and 3 can reach this point.
1213    // As a result, we know there's exactly one written register.
1214    assert(writtenRegs.size() == 1);
1215    MachRegister written = (*writtenRegs.begin())->getID();
1216    Absloc writtenloc(written);
1217
1218
1219    if (insn->readsMemory()) {
1220       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1221          operands[1].format(arch).c_str());
1222
1223       // Extract the expression inside the dereference
1224       std::vector<Expression::Ptr> addrExpr;
1225       operands[1].getValue()->getChildren(addrExpr);
1226       assert(addrExpr.size() == 1);
1227
1228       // Try to determine the read memory address
1229       PCRelativeVisitor visitor(off, insn);
1230       addrExpr[0]->apply(&visitor);
1231       if (visitor.isDefined()) {
1232          // Case 3a
1233          Address readAddr = visitor.getResult();
1234          stackanalysis_printf("\t\t\tSimplifies to: %lx\n", readAddr);
1235          Absloc from(readAddr);
1236          xferFuncs.push_back(TransferFunc::aliasFunc(from, writtenloc));
1237       } else {
1238          // Case 3b
1239          stackanalysis_printf("\t\t\tCan't determine statically\n");
1240          xferFuncs.push_back(TransferFunc::bottomFunc(writtenloc));
1241       }
1242       return;
1243    }
1244
1245
1246    // Only Cases 1 and 2 can reach this point.
1247    // As a result, we know there's either 0 or 1 read registers
1248    MachRegister read;
1249    if (!readRegs.empty()) {
1250       assert(readRegs.size() == 1);
1251       read = (*readRegs.begin())->getID();
1252    }
1253    Absloc readloc(read);
1254
1255
1256    if (read.isValid()) {
1257       // Case 1
1258       stackanalysis_printf("\t\t\t Alias detected: %s -> %s\n",
1259          read.name().c_str(), written.name().c_str());
1260       xferFuncs.push_back(TransferFunc::aliasFunc(readloc, writtenloc));
1261    } else {
1262       // Case 2
1263       InstructionAPI::Expression::Ptr readExpr = operands[1].getValue();
1264       stackanalysis_printf("\t\t\t\t readOperand = %s\n",
1265          readExpr->format().c_str());
1266
1267       if (typeid(*readExpr) == typeid(InstructionAPI::Immediate)) {
1268          long readValue = readExpr->eval().convert<long>();
1269          stackanalysis_printf(
1270             "\t\t\t Immediate to register move: %s set to %ld\n",
1271             written.name().c_str(), readValue);
1272          xferFuncs.push_back(TransferFunc::absFunc(writtenloc, readValue));
1273       } else {
1274          // This case is not expected to occur
1275          stackanalysis_printf("\t\t\t Unhandled move: %s set to BOTTOM\n",
1276             written.name().c_str());
1277          xferFuncs.push_back(TransferFunc::bottomFunc(writtenloc));
1278       }
1279       return;
1280    }
1281 }
1282
1283 void StackAnalysis::handleZeroExtend(Instruction::Ptr insn,
1284    TransferFuncs &xferFuncs) {
1285
1286    // This instruction zero extends the read register into the written register
1287
1288    // Don't care about memory stores
1289    if (insn->writesMemory()) return;
1290
1291    MachRegister read;
1292    MachRegister written;
1293    std::set<RegisterAST::Ptr> regs;
1294    RegisterAST::Ptr reg;
1295
1296    insn->getWriteSet(regs);
1297
1298    // There can only be 0 or 1 target regs. Since we short-circuit the case
1299    // where the target is memory, there must be exactly 1 target reg.
1300    assert(regs.size() == 1);
1301    reg = *(regs.begin());
1302    written = reg->getID();
1303    regs.clear();
1304
1305    Absloc writtenloc(written);
1306
1307    // Handle memory loads
1308    if (insn->readsMemory()) {
1309       xferFuncs.push_back(TransferFunc::bottomFunc(writtenloc));
1310       return;
1311    }
1312
1313    insn->getReadSet(regs);
1314    if (regs.size() != 1) {
1315       stackanalysis_printf(
1316          "\t\t\t Unhandled zero extend, setting %s = BOTTOM\n",
1317          written.name().c_str());
1318       xferFuncs.push_back(TransferFunc::bottomFunc(writtenloc));
1319       return;
1320    }
1321    reg = *(regs.begin());
1322    read = reg->getID();
1323    Absloc readloc(read);
1324
1325
1326    stackanalysis_printf("\t\t\t Alias detected: %s -> %s\n",
1327       read.name().c_str(), written.name().c_str());
1328    xferFuncs.push_back(TransferFunc::aliasFunc(readloc, writtenloc));
1329 }
1330
1331 void StackAnalysis::handleSignExtend(Instruction::Ptr insn,
1332    TransferFuncs &xferFuncs) {
1333
1334    // This instruction sign extends the read register into the written
1335    // register. Aliasing insn't really correct here...sign extension is going
1336    // to change the value...
1337
1338    // Don't care about memory stores
1339    if (insn->writesMemory()) return;
1340
1341    MachRegister read;
1342    MachRegister written;
1343    std::set<RegisterAST::Ptr> regs;
1344    RegisterAST::Ptr reg;
1345
1346    insn->getWriteSet(regs);
1347
1348    // There can only be 0 or 1 target regs. Since we short-circuit the case
1349    // where the target is memory, there must be exactly 1 target reg.
1350    assert(regs.size() == 1);
1351    reg = *(regs.begin());
1352    written = reg->getID();
1353    regs.clear();
1354
1355    Absloc writtenloc(written);
1356
1357    // Handle memory loads
1358    if (insn->readsMemory()) {
1359       xferFuncs.push_back(TransferFunc::bottomFunc(writtenloc));
1360       return;
1361    }
1362
1363    insn->getReadSet(regs);
1364    if (regs.size() != 1) {
1365       stackanalysis_printf(
1366          "\t\t\t Unhandled sign extend, setting %s = BOTTOM\n",
1367          written.name().c_str());
1368       xferFuncs.push_back(TransferFunc::bottomFunc(writtenloc));
1369       return;
1370    }
1371    reg = *(regs.begin());
1372    read = reg->getID();
1373
1374    Absloc readloc(read);
1375
1376    stackanalysis_printf(
1377       "\t\t\t Sign extend insn detected: %s -> %s (must be top or bottom)\n",
1378       read.name().c_str(), written.name().c_str());
1379    xferFuncs.push_back(TransferFunc::aliasFunc(readloc, writtenloc, true));
1380    return;
1381 }
1382
1383 void StackAnalysis::handleDefault(Instruction::Ptr insn,
1384    TransferFuncs &xferFuncs) {
1385
1386    std::set<RegisterAST::Ptr> written;
1387    insn->getWriteSet(written);
1388    for (std::set<RegisterAST::Ptr>::iterator iter = written.begin(); 
1389         iter != written.end(); ++iter) {
1390
1391       Absloc loc((*iter)->getID());
1392       xferFuncs.push_back(TransferFunc::aliasFunc(loc, loc, true));
1393       stackanalysis_printf(
1394          "\t\t\t Unhandled insn %s detected: %s set to topBottom\n",
1395          insn->format().c_str(), (*iter)->getID().name().c_str());
1396    }
1397    return;
1398 }
1399
1400 bool StackAnalysis::isCall(Instruction::Ptr insn) {
1401    return insn->getCategory() == c_CallInsn;
1402 }
1403
1404 bool StackAnalysis::handleNormalCall(Instruction::Ptr insn, Block *block,
1405    Offset off, TransferFuncs &xferFuncs) {
1406
1407    if (!insn->getControlFlowTarget()) return false;
1408
1409    // Must be a thunk based on parsing.
1410    if (off != block->lastInsnAddr()) return false;
1411    
1412    // Top caller-save registers
1413    // Bottom return registers
1414    ABI* abi = ABI::getABI(word_size);
1415    const bitArray callWritten = abi->getCallWrittenRegisters();
1416    const bitArray returnRegs = abi->getReturnRegisters();
1417    for (auto iter = abi->getIndexMap()->begin();
1418         iter != abi->getIndexMap()->end();
1419         ++iter) {
1420        // We only care about GPRs right now
1421       unsigned int gpr;
1422       Architecture arch = insn->getArch();
1423       switch(arch) {
1424          case Arch_x86:
1425             gpr = x86::GPR;
1426             break;
1427          case Arch_x86_64:
1428             gpr = x86_64::GPR;
1429             break;
1430          case Arch_ppc32:
1431             gpr = ppc32::GPR;
1432             break;
1433          case Arch_ppc64:
1434             gpr = ppc64::GPR;
1435             break;
1436          default:
1437             handleDefault(insn, xferFuncs);
1438             return true;
1439       };
1440       if ((*iter).first.regClass() == gpr) {
1441          if (callWritten.test((*iter).second)) {
1442             Absloc loc((*iter).first);
1443             if (returnRegs.test((*iter).second)) {
1444                // Bottom
1445                xferFuncs.push_back(TransferFunc::bottomFunc(loc));
1446             } else {
1447                // Top
1448                xferFuncs.push_back(TransferFunc::retopFunc(loc));
1449             }
1450          }
1451       }
1452    }
1453
1454    const Block::edgelist & outs = block->targets();  
1455    Block::edgelist::const_iterator eit = outs.begin();
1456    for ( ; eit != outs.end(); ++eit) {
1457       Edge *cur_edge = (Edge*)*eit;
1458
1459       Absloc sploc(sp());
1460
1461       if (cur_edge->type() == DIRECT) {
1462          // For some reason we're treating this
1463          // call as a branch. So it shifts the stack
1464          // like a push (heh) and then we're done.
1465          stackanalysis_printf(
1466             "\t\t\t Stack height changed by simulate-jump call\n");
1467          xferFuncs.push_back(TransferFunc::deltaFunc(sploc, -1 * word_size));
1468          return true;
1469       }
1470       
1471       if (cur_edge->type() != CALL) 
1472          continue;
1473       
1474       Block *target_bbl = cur_edge->trg();
1475       Function *target_func = target_bbl->obj()->findFuncByEntry(
1476          target_bbl->region(), target_bbl->start());
1477       
1478       if (!target_func)
1479          continue;
1480       
1481       Height h = getStackCleanAmount(target_func);
1482       if (h == Height::bottom) {
1483          stackanalysis_printf(
1484             "\t\t\t Stack height changed by self-cleaning function: bottom\n");
1485          xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1486       }
1487       else {
1488          stackanalysis_printf(
1489             "\t\t\t Stack height changed by self-cleaning function: %ld\n",
1490             h.height());
1491          xferFuncs.push_back(TransferFunc::deltaFunc(sploc, h.height()));
1492       }
1493       return true;
1494
1495    }
1496    stackanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
1497    return true;
1498 }
1499                                        
1500
1501 bool StackAnalysis::handleThunkCall(Instruction::Ptr insn,
1502    TransferFuncs &xferFuncs) {
1503
1504    // We know that we're not a normal call, so it depends on whether
1505    // the CFT is "next instruction" or not. 
1506    if (insn->getCategory() != c_CallInsn ||
1507        !insn->getControlFlowTarget()) return false;
1508
1509    // Eval of getCFT(0) == size?
1510    Expression::Ptr cft = insn->getControlFlowTarget();
1511    cft->bind(thePC.get(), Result(u32, 0));
1512    Result res = cft->eval();
1513    if (!res.defined) return false;
1514    if (res.convert<unsigned>() == insn->size()) {
1515       Absloc sploc(sp());
1516       xferFuncs.push_back(TransferFunc::deltaFunc(sploc, -1 * word_size));
1517       return true;
1518    }
1519    // Else we're calling a mov, ret thunk that has no effect on the stack pointer
1520    return true;
1521 }
1522
1523
1524 void StackAnalysis::createEntryInput(AbslocState &input) {
1525    // FIXME for POWER/non-IA32
1526    // IA32 - the in height includes the return address and therefore
1527    // is <wordsize>
1528    // POWER - the in height is 0
1529
1530 #if defined(arch_power)
1531    input[Absloc(sp())] = Height(0);
1532 #elif (defined(arch_x86) || defined(arch_x86_64))
1533    input[Absloc(sp())] = Height(-1 * word_size);
1534 #else
1535    assert(0 && "Unimplemented architecture");
1536 #endif
1537 }
1538
1539 StackAnalysis::AbslocState StackAnalysis::getSrcOutputLocs(Edge* e) {
1540    Block* b = e->src();
1541    stackanalysis_printf("%lx ", b->lastInsnAddr());
1542    return blockOutputs[b];
1543 }
1544
1545 void StackAnalysis::meetInputs(Block *block, AbslocState& blockInput,
1546    AbslocState &input) {
1547
1548    input.clear();
1549
1550    //Intraproc epred; // ignore calls, returns in edge iteration
1551    //NoSinkPredicate epred2(&epred); // ignore sink node (unresolvable)
1552    intra_nosink epred2;
1553    
1554    stackanalysis_printf("\t ... In edges: ");
1555    const Block::edgelist & inEdges = block->sources();
1556    std::for_each(
1557       boost::make_filter_iterator(epred2, inEdges.begin(), inEdges.end()),
1558       boost::make_filter_iterator(epred2, inEdges.end(), inEdges.end()),
1559       boost::bind(&StackAnalysis::meet, this,
1560          boost::bind(&StackAnalysis::getSrcOutputLocs, this, _1),
1561          boost::ref(input)));
1562    stackanalysis_printf("\n");
1563
1564    meet(blockInput, input);
1565 }
1566
1567 void StackAnalysis::meet(const AbslocState &input, AbslocState &accum) {
1568    for (AbslocState::const_iterator iter = input.begin();
1569         iter != input.end(); ++iter) {
1570       accum[iter->first] = Height::meet(iter->second, accum[iter->first]);
1571    }
1572 }
1573
1574 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::deltaFunc(Absloc r, long d) {
1575    return TransferFunc(uninitialized, d, Absloc(), r);
1576 }
1577
1578 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::absFunc(Absloc r, long a, bool i) {
1579    return TransferFunc(a, 0, Absloc(), r, i);
1580 }
1581
1582 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::aliasFunc(Absloc f, Absloc t, bool i) {
1583    return TransferFunc (uninitialized, 0, f, t, i);
1584 }
1585
1586 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::bottomFunc(Absloc r) {
1587    return TransferFunc(notUnique, notUnique, Absloc(), r);
1588 }
1589
1590 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::retopFunc(Absloc r) {
1591    return TransferFunc(uninitialized, 0, Absloc(), r, false, true);
1592 }
1593
1594 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::sibFunc(
1595    std::map<Absloc, std::pair<long,bool> > f, long d, Absloc t) {
1596    return TransferFunc(f, d, t);
1597 }
1598
1599 bool StackAnalysis::TransferFunc::isBottom() const {
1600    return (delta == notUnique || abs == notUnique) && !from.isValid() &&
1601       !isSIB();
1602 }
1603
1604 bool StackAnalysis::TransferFunc::isTop() const {
1605    return !isDelta() && !isAbs() && !isAlias() && !isSIB() && !isBottom() &&
1606       abs == uninitialized;
1607 }
1608
1609 bool StackAnalysis::TransferFunc::isRetop() const {
1610    return isTop() && retop;
1611 }
1612
1613 bool StackAnalysis::TransferFunc::isAlias() const {
1614    return from.isValid();
1615 }
1616
1617 bool StackAnalysis::TransferFunc::isAbs() const {
1618    return (abs != uninitialized && abs != notUnique);
1619 }
1620
1621 bool StackAnalysis::TransferFunc::isDelta() const {
1622    return (delta != 0);
1623 }
1624
1625 bool StackAnalysis::TransferFunc::isSIB() const {
1626     return (fromRegs.size() > 0);
1627 }
1628
1629
1630
1631 // Destructive update of the input map. Assumes inputs are absolute,
1632 // uninitalized, or bottom; no deltas.
1633 StackAnalysis::Height StackAnalysis::TransferFunc::apply(
1634    const AbslocState &inputs) const {
1635    assert(target.isValid());
1636    // Bottom stomps everything
1637    if (isBottom()) {
1638       return Height::bottom;
1639    }
1640
1641    AbslocState::const_iterator iter = inputs.find(target);
1642    Height input;
1643    if (iter != inputs.end()) {
1644       input = iter->second;
1645    }
1646    else {
1647       input = Height::top;
1648    }
1649
1650    bool isTopBottomOrig = isTopBottom();
1651
1652    if (isSIB()) {
1653       input = Height::top; // SIB overwrites, so start at TOP
1654       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
1655          Absloc curLoc = (*iter).first;
1656          long curScale = (*iter).second.first;
1657          bool curTopBottom = (*iter).second.second;
1658          auto findLoc = inputs.find(curLoc);
1659          Height locInput;
1660          if (findLoc == inputs.end()) {
1661             locInput = Height::top;
1662          } else {
1663             locInput = findLoc->second;
1664          }
1665
1666          if (locInput == Height::top) {
1667             // This term doesn't affect our end result, so it can be safely
1668             // ignored.
1669          } else if (locInput == Height::bottom) {
1670             if (curScale == 1) {
1671                // Must bottom everything only if the scale is 1.  Otherwise,
1672                // any stack height will be obfuscated.
1673                input = Height::bottom;
1674                break;
1675             }
1676          } else {
1677             if (curScale == 1) {
1678                // If the scale isn't 1, then any stack height is obfuscated,
1679                // and we can safely ignore the term.
1680                if (curTopBottom) {
1681                   input = Height::bottom;
1682                   break;
1683                } else {
1684                   input += locInput; // Matt: Always results in bottom?
1685                }
1686             }
1687          }
1688       }
1689    }
1690
1691    if (isAbs()) {
1692       // We cannot be an alias, as the absolute removes that. 
1693       assert(!isAlias());
1694       // Apply the absolute
1695       // NOTE: an absolute is not a stack height, set input to top
1696       //input = abs;
1697       input = Height::top;
1698    }
1699    if (isAlias()) {
1700       // Cannot be absolute
1701       assert(!isAbs());
1702       // Copy the input value from whatever we're an alias of.
1703       AbslocState::const_iterator iter2 = inputs.find(from);
1704       if (iter2 != inputs.end()) input = iter2->second;
1705       else input = Height::top;
1706    }
1707    if (isDelta()) {
1708       input += delta;
1709    }
1710    if (isRetop()) {
1711       input = Height::top;
1712    }
1713    if (isTopBottomOrig) {
1714       if (!input.isTop()) {
1715          input = Height::bottom;
1716       }
1717    }
1718    return input;
1719 }
1720
1721 // Accumulation to the input map. This is intended to create a summary, so we
1722 // create something that can take further input.
1723 void StackAnalysis::TransferFunc::accumulate(
1724    std::map<Absloc, TransferFunc> &inputs) {
1725    TransferFunc &input = inputs[target];
1726    if (input.target.isValid()) assert(input.target == target);
1727    input.target = target; // Default constructed TransferFuncs won't have this
1728    assert(target.isValid());
1729
1730    // Bottom stomps everything
1731    if (isBottom()) {
1732       input = bottomFunc(target);
1733       return;
1734    }
1735    bool isTopBottomOrig = isTopBottom();
1736    if (!input.isTopBottom() && !input.isRetop()) {
1737       input.topBottom = isTopBottomOrig;
1738    }
1739    // Absolutes override everything else
1740    if (isAbs()) {
1741       input = absFunc(target, abs, isTopBottomOrig);
1742       return;
1743    }
1744    if (isSIB()) {
1745       // First check for special cases
1746       bool allAbs = true;
1747       bool allToppable = true;
1748       bool anyBottomed = false;
1749       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); iter++) {
1750          Absloc fromLocOrig = iter->first;
1751          long scaleOrig = iter->second.first;
1752          auto inputEntry = inputs.find(fromLocOrig);
1753          if (inputEntry == inputs.end()) {
1754             allAbs = false;
1755             if (scaleOrig == 1) {
1756                allToppable = false;
1757             }
1758          } else {
1759             if (inputEntry->second.isBottom() && scaleOrig == 1) {
1760                anyBottomed = true;
1761             }
1762             if (!inputEntry->second.isRetop() && !inputEntry->second.isAbs() &&
1763                scaleOrig == 1) {
1764                allToppable = false;
1765             }
1766             if (!inputEntry->second.isAbs()) {
1767                allAbs = false;
1768             }
1769          }
1770       }
1771
1772       // Now handle special cases
1773       if (anyBottomed) {
1774          input = bottomFunc(target);
1775          return;
1776       }
1777       if (allAbs) {
1778          long newDelta = delta;
1779          for (auto iter = fromRegs.begin(); iter != fromRegs.end(); iter++) {
1780             Absloc fromLocOrig = iter->first;
1781             long scaleOrig = iter->second.first;
1782             TransferFunc inputAbsFunc = inputs.find(fromLocOrig)->second;
1783             newDelta += inputAbsFunc.abs * scaleOrig;
1784          }
1785          input = absFunc(target, newDelta);
1786          return;
1787       }
1788       if (allToppable) {
1789          input = retopFunc(target);
1790          return;
1791       }
1792
1793       // Handle default case
1794       std::map<Absloc, std::pair<long,bool> > newFromRegs;
1795       long newDelta = delta;
1796       bool anyToppedTerms = false;
1797       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
1798          Absloc fromLocOrig = (*iter).first;
1799          long scaleOrig = (*iter).second.first;
1800
1801          // Because any term with a scale > 1 is TOP, such terms do not affect
1802          // the final TOP/BOTTOM/Height value of the LEA and can be ignored.
1803          // FIXME if we change apply() to include constant propagation
1804          if (scaleOrig > 1) {
1805             anyToppedTerms = true;
1806             continue;
1807          }
1808
1809          auto findLoc = inputs.find(fromLocOrig);
1810          if (findLoc == inputs.end()) {
1811             // Easy case
1812             // Only add the term if we're not already tracking that register.
1813             // FIXME if we change apply() to include constant propagation
1814             auto found = newFromRegs.find(fromLocOrig);
1815             if (found == newFromRegs.end()) {
1816                newFromRegs.insert(make_pair(fromLocOrig,
1817                   make_pair(scaleOrig, false)));
1818             }
1819          } else {
1820             TransferFunc fromRegFunc = findLoc->second;
1821             assert(!fromRegFunc.isBottom());  // Should be special case
1822             if (fromRegFunc.isAbs()) {
1823                newDelta += fromRegFunc.abs * scaleOrig;
1824             }
1825             if (fromRegFunc.isSIB()) {
1826                // Replace registers and update scales
1827                for (auto regIter = fromRegFunc.fromRegs.begin();
1828                   regIter != fromRegFunc.fromRegs.end(); ++regIter) {
1829                   Absloc replaceLoc = regIter->first;
1830                   long replaceScale = regIter->second.first;
1831                   bool replaceTopBottom = regIter->second.second;
1832                   long newScale = replaceScale * scaleOrig;
1833
1834                   // Add to our map only the registers that we aren't already
1835                   // considering.
1836                   // FIXME if we change apply() to include constant propagation
1837                   auto found = newFromRegs.find(replaceLoc);
1838                   if (found == newFromRegs.end()) {
1839                      newFromRegs.insert(make_pair(replaceLoc,
1840                         make_pair(newScale, replaceTopBottom)));
1841                   }
1842                }
1843             }
1844             if (fromRegFunc.isAlias()) {
1845                // Replace fromRegOrig with fromRegFunc.from only if we aren't
1846                // already considering fromRegFunc.from in our map.
1847                // FIXME if we change apply() to include constant propagation
1848                auto found = newFromRegs.find(fromRegFunc.from);
1849                if (found == newFromRegs.end()) {
1850                   newFromRegs.insert(make_pair(fromRegFunc.from,
1851                      make_pair(scaleOrig, fromRegFunc.isTopBottom())));
1852                }
1853             }
1854             if (fromRegFunc.isDelta()) {
1855                newDelta += fromRegFunc.delta * scaleOrig;
1856                if (!fromRegFunc.isAlias() && !fromRegFunc.isSIB() &&
1857                   !fromRegFunc.isAbs()) {
1858                   // Add the register back in...
1859                   // FIXME if we change apply() to include constant propagation
1860                   auto found = newFromRegs.find(fromLocOrig);
1861                   if (found == newFromRegs.end()) {
1862                      newFromRegs.insert(make_pair(fromLocOrig,
1863                         make_pair(scaleOrig,false)));
1864                   }
1865                }
1866             }
1867             if (fromRegFunc.isRetop()) {
1868                // This is a register that was re-topped due to an instruction
1869                // in this block.  Thus this term is TOP and doesn't affect the
1870                // value of the LEA, so we can ignore it.
1871                // FIXME if we change apply() to include constant propagation
1872                continue;
1873             }
1874             if (fromRegFunc.isTop()) {
1875                // This is the default constructed target when the target didn't
1876                // already exist.  Keep track of this register unless we already
1877                // are.
1878                // FIXME if we change apply() to include constant propagation
1879                auto found = newFromRegs.find(fromLocOrig);
1880                if (found == newFromRegs.end()) {
1881                   newFromRegs.insert(make_pair(fromLocOrig,
1882                      make_pair(scaleOrig,false)));
1883                }
1884             }
1885          }
1886       }
1887
1888       if (anyToppedTerms) {
1889          // If any term is later discovered to be a stack height, we need to
1890          // bottom the target register since this SIB contains a topped term
1891          // (we know the topped term isn't a stack height, but we don't know
1892          // precisely what it is).  We indicate this by setting the
1893          // topBottom flag on non-topped registers.
1894          for (auto iter = newFromRegs.begin(); iter != newFromRegs.end();
1895             iter++) {
1896             iter->second.second = true;
1897          }
1898       }
1899
1900       input = sibFunc(newFromRegs, newDelta, target);
1901       input.topBottom = isTopBottomOrig;
1902       return;
1903    }
1904
1905    // Aliases can be tricky
1906    // apply alias logic only if registers are different
1907    if (isAlias() && target != from) {
1908       // We need to record that we want to take the inflow height
1909       // of a different register. 
1910       // Don't do an inputs[from] as that creates
1911       std::map<Absloc, TransferFunc>::iterator iter = inputs.find(from);
1912       if (iter == inputs.end()) {
1913          // Aliasing to something we haven't seen yet; easy
1914          input = *this;
1915          input.topBottom = isTopBottomOrig;
1916          return;
1917       }
1918
1919       TransferFunc &alias = iter->second;
1920
1921       if (alias.isAbs()) {
1922          // We reset the height, so we don't care about the inflow height
1923          assert(!alias.isAlias());
1924          input = absFunc(input.target, alias.abs);
1925          input.topBottom = isTopBottomOrig || alias.isTopBottom();
1926          assert(input.target.isValid());
1927
1928          if (isDelta()) {
1929             input.delta += delta;
1930          }
1931          return;
1932       }
1933       if (alias.isAlias()) {
1934          assert(!alias.isAbs());
1935          input = alias;
1936          input.target = target;
1937          input.topBottom = isTopBottomOrig || alias.isTopBottom();
1938          assert(input.target.isValid());
1939
1940          if (isDelta()) {
1941             input.delta += delta;
1942          }
1943          return;
1944       }
1945       if (alias.isSIB()) {
1946          input = alias;
1947          input.target = target;
1948          input.topBottom = isTopBottomOrig;
1949
1950          if (isDelta()) {
1951              input.delta += delta;
1952          }
1953
1954          return;
1955       }
1956
1957       // without bottom we mess up in the default case.
1958       if (alias.isBottom()) {
1959          input = bottomFunc(target);
1960          return;
1961       }
1962
1963       if (alias.isRetop()) {
1964          input = retopFunc(target);
1965          return;
1966       }
1967
1968       // Default case: record the alias, zero out everything else, copy over
1969       // the delta if it's defined.
1970       //input.target is defined
1971       input.from = alias.target;
1972       input.abs = uninitialized;
1973       if (alias.isDelta()) {
1974          input.delta = alias.delta;
1975       } else {
1976          input.delta = 0;
1977       }
1978       input.topBottom = isTopBottomOrig || alias.isTopBottom();
1979       input.fromRegs.clear();
1980    }
1981
1982    if (isDelta() && !input.isRetop()) {
1983       input.delta += delta;
1984    }
1985
1986    if (isRetop()) {
1987       input = *this;
1988    }
1989 }
1990
1991
1992 void StackAnalysis::SummaryFunc::apply(const AbslocState &in,
1993    AbslocState &out) const {
1994
1995    // Copy all the elements we don't have xfer funcs for.
1996    out = in;
1997
1998    // Apply in parallel since all summary funcs are from the start of the block
1999    for (TransferSet::const_iterator iter = accumFuncs.begin();
2000       iter != accumFuncs.end(); ++iter) {
2001       assert(iter->first.isValid());
2002       out[iter->first] = iter->second.apply(in);
2003    }
2004 }
2005
2006
2007 void StackAnalysis::SummaryFunc::add(TransferFuncs &xferFuncs) {
2008    // We need to update our register->xferFunc map
2009    // with the effects of each of the transferFuncs. 
2010    
2011    for (TransferFuncs::iterator iter = xferFuncs.begin(); 
2012         iter != xferFuncs.end(); ++iter) {
2013       TransferFunc &func = *iter;
2014
2015       func.accumulate(accumFuncs);
2016       validate();
2017    }
2018
2019 }
2020
2021 void StackAnalysis::SummaryFunc::validate() const {
2022    for (TransferSet::const_iterator iter = accumFuncs.begin(); 
2023         iter != accumFuncs.end(); ++iter)
2024    {
2025       const TransferFunc &func = iter->second;
2026       assert(func.target.isValid());
2027       if (func.isAlias()) assert(!func.isAbs());
2028       if (func.isAbs()) assert(!func.isAlias());
2029       if (func.isBottom()) assert(!func.isAlias());
2030    }
2031 }
2032
2033 MachRegister StackAnalysis::sp() { 
2034    return MachRegister::getStackPointer(func->isrc()->getArch());
2035 }
2036
2037 MachRegister StackAnalysis::fp() { 
2038    return MachRegister::getFramePointer(func->isrc()->getArch());
2039 }
2040
2041 std::string StackAnalysis::format(const AbslocState &input) const {
2042    std::stringstream ret;
2043    for (AbslocState::const_iterator iter = input.begin();
2044       iter != input.end(); ++iter) {
2045       ret << iter->first.format() << " := " << iter->second.format() << ", ";
2046    }
2047    return ret.str();
2048 }
2049
2050 // Converts a delta in a Result to a long
2051 long StackAnalysis::extractDelta(Result deltaRes) {
2052    long delta;
2053    switch(deltaRes.size()) {
2054       case 1:
2055          delta = (long)deltaRes.convert<int8_t>();
2056          break;
2057       case 2:
2058          delta = (long)deltaRes.convert<int16_t>();
2059          break;
2060       case 4:
2061          delta = (long)deltaRes.convert<int32_t>();
2062          break;
2063       case 8:
2064          delta = (long)deltaRes.convert<int64_t>();
2065          break;
2066       default:
2067          assert(0);
2068    }
2069    return delta;
2070 }