Implemented basic memory tracking for stack analysis.
[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
192
193    worklist.push(func->entry());
194
195    Block *entry = func->entry();
196
197    while (!worklist.empty()) {
198       Block *block = worklist.front();
199       stackanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n",
200          block->start());
201
202       worklist.pop();
203
204       // Step 1: calculate the meet over the heights of all incoming
205       // intraprocedural blocks.
206
207       AbslocState input;
208
209       if (block == entry) {
210          createEntryInput(input);
211          stackanalysis_printf("\t Primed initial block\n");
212       }
213       else {
214          stackanalysis_printf("\t Calculating meet with block [%x-%x]\n",
215             block->start(), block->lastInsnAddr());
216          meetInputs(block, blockInputs[block], input);
217       }
218
219       stackanalysis_printf("\t New in meet: %s\n", format(input).c_str());
220
221       // Step 2: see if the input has changed
222
223       if (input == blockInputs[block]) {
224          // No new work here
225          stackanalysis_printf("\t ... equal to current, skipping block\n");
226          continue;
227       }
228
229       stackanalysis_printf("\t ... inequal to current %s, analyzing block\n",
230          format(blockInputs[block]).c_str());
231
232       blockInputs[block] = input;
233
234       // Step 3: calculate our new outs
235
236       blockEffects[block].apply(input, blockOutputs[block]);
237
238       stackanalysis_printf("\t ... output from block: %s\n",
239          format(blockOutputs[block]).c_str());
240
241       // Step 4: push all children on the worklist.
242
243       const Block::edgelist & outEdges = block->targets();
244       std::for_each(
245          boost::make_filter_iterator(epred2, outEdges.begin(), outEdges.end()),
246          boost::make_filter_iterator(epred2, outEdges.end(), outEdges.end()),
247          boost::bind(add_target, boost::ref(worklist), _1)
248       );
249    }
250 }
251
252
253
254 void StackAnalysis::summarize() {
255     // Now that we know the actual inputs to each block,
256     // we create intervals by replaying the effects of each
257     // instruction.
258
259     intervals_ = new Intervals();
260
261     Function::blocklist bs = func->blocks();
262     Function::blocklist::iterator bit = bs.begin();
263     for ( ; bit != bs.end(); ++bit) {
264         Block *block = *bit;
265         AbslocState input = blockInputs[block];
266
267         std::map<Offset, TransferFuncs>::iterator iter;
268         for (iter = insnEffects[block].begin();
269             iter != insnEffects[block].end(); ++iter) {
270             Offset off = iter->first;
271             TransferFuncs &xferFuncs = iter->second;
272
273             // TODO: try to collapse these in some intelligent fashion
274             (*intervals_)[block][off] = input;
275
276             for (TransferFuncs::iterator iter2 = xferFuncs.begin();
277                 iter2 != xferFuncs.end(); ++iter2) {
278                 input[iter2->target] = iter2->apply(input);
279             }
280         }
281         (*intervals_)[block][block->end()] = input;
282
283         assert(input == blockOutputs[block]);
284     }
285 }
286
287 void StackAnalysis::computeInsnEffects(ParseAPI::Block *block,
288                                        Instruction::Ptr insn,
289                                        const Offset off,
290                                        TransferFuncs &xferFuncs) {
291     stackanalysis_printf("\t\tInsn at 0x%lx\n", off);
292     entryID what = insn->getOperation().getID();
293
294     // Reminder: what we're interested in:
295     // a) Use of the stack pointer to define another register
296     //      Assumption: this is done by an e_mov and is a direct copy
297     //                  else bottom
298     // b) Use of another register to define the stack pointer
299     //      Assumption: see ^^
300     // c) Modification of the stack pointer
301     // 
302     // The reason for these assumptions is to keep the analysis reasonable; also,
303     // other forms just don't occur. 
304     //
305     // In summary, the stack pointer must be read or written for us to be interested.
306     // 
307     // However, we need to detect when a register is destroyed. So if something is written,
308     // we assume it is destroyed.
309     // 
310     // For now, we assume an all-to-all mapping for speed. 
311
312     // Cases we handle
313     if (isCall(insn)) {
314        if (handleNormalCall(insn, block, off, xferFuncs))
315           return;
316        else if (handleThunkCall(insn, xferFuncs))
317           return;
318        else
319           return handleDefault(insn, xferFuncs);
320     }
321
322     int sign = 1;
323     switch (what) {
324        case e_push:
325           sign = -1;
326           //FALLTHROUGH
327        case e_pop:
328           handlePushPop(insn, sign, xferFuncs);
329           break;
330        case e_ret_near:
331        case e_ret_far:
332           handleReturn(insn, xferFuncs);
333           break;
334        case e_lea:
335          handleLEA(insn, xferFuncs);
336          break;
337        case e_sub:
338           sign = -1;
339           //FALLTHROUGH
340        case e_add:
341           handleAddSub(insn, sign, xferFuncs);
342           break;
343        case e_leave:
344           handleLeave(xferFuncs);
345           break;
346        case e_pushfd:
347           sign = -1;
348           //FALLTHROUGH
349        case e_popfd:
350           handlePushPopFlags(sign, xferFuncs);
351           break;
352        case e_pushad:
353            sign = -1;
354            handlePushPopRegs(sign, xferFuncs);
355            break;
356        case e_popad:
357            // This nukes all registers
358            handleDefault(insn, xferFuncs);
359            break;
360        case power_op_addi:
361        case power_op_addic:
362           handlePowerAddSub(insn, sign, xferFuncs);
363           break;
364        case power_op_stwu:
365           handlePowerStoreUpdate(insn, xferFuncs);
366           break;
367        case e_mov:
368           handleMov(insn, off, xferFuncs);
369           break;
370        case e_movzx:
371           handleZeroExtend(insn, xferFuncs);
372           break;
373        case e_movsx:
374        case e_movsxd:
375        case e_cbw:
376        case e_cwde:
377           handleSignExtend(insn, xferFuncs);
378           break;
379        case e_xor:
380           handleXor(insn, xferFuncs);
381           break;
382        default:
383           handleDefault(insn, xferFuncs);
384     }
385 }
386
387 StackAnalysis::Height StackAnalysis::getStackCleanAmount(Function *func) {
388     // Cache previous work...
389     if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
390         return funcCleanAmounts[func];
391     }
392
393     if (!func->cleansOwnStack()) {
394         funcCleanAmounts[func] = 0;
395         return funcCleanAmounts[func];
396     }
397
398     InstructionDecoder decoder((const unsigned char*)NULL, 0, func->isrc()->getArch());
399     unsigned char *cur;
400
401     std::set<Height> returnCleanVals;
402
403     Function::const_blocklist returnBlocks = func->returnBlocks();
404     auto rets = returnBlocks.begin();
405     for (; rets != returnBlocks.end(); ++rets) {
406          Block *ret = *rets;
407          cur = (unsigned char *) ret->region()->getPtrToInstruction(ret->lastInsnAddr());
408          Instruction::Ptr insn = decoder.decode(cur);
409
410          entryID what = insn->getOperation().getID();
411          if (what != e_ret_near)
412              continue;
413       
414          int val;
415          std::vector<Operand> ops;
416          insn->getOperands(ops);
417          if (ops.size() == 1) {
418              val = 0;
419          } else {
420              Result imm = ops[1].getValue()->eval();
421              assert(imm.defined);
422              val = (int) imm.val.s16val;
423          }
424          returnCleanVals.insert(Height(val));
425     }
426
427         Height clean = Height::meet(returnCleanVals);
428         if (clean == Height::top) {
429                 // Non-returning or tail-call exits?
430                 clean = Height::bottom;
431         }
432
433     funcCleanAmounts[func] = clean;
434
435     return clean;
436 }
437
438 StackAnalysis::StackAnalysis() :
439    func(NULL), intervals_(NULL), word_size(0) {};
440    
441
442 StackAnalysis::StackAnalysis(Function *f) : func(f),
443                                             intervals_(NULL) {
444    word_size = func->isrc()->getAddressWidth();
445    theStackPtr = Expression::Ptr(new RegisterAST(MachRegister::getStackPointer(func->isrc()->getArch())));
446    thePC = Expression::Ptr(new RegisterAST(MachRegister::getPC(func->isrc()->getArch())));
447 };
448
449 void StackAnalysis::debug() {
450 }
451
452 std::string StackAnalysis::TransferFunc::format() const {
453    std::stringstream ret;
454
455    ret << "[";
456    if (target.isValid())
457       ret << target.format();
458    else
459       ret << "<INVALID>";
460    ret << ":=";
461    if (isBottom()) ret << "<BOTTOM>";
462    else if (isTop()) ret << "<TOP>";
463    else {
464       bool foundType = false;
465       if (isAlias()) {
466          ret << from.format();
467          foundType = true;
468       }
469       if (isAbs()) {
470          ret << abs << dec;
471          foundType = true;
472       }
473       if (isSIB()) {
474           for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
475               if (iter != fromRegs.begin()) {
476                   ret << "+";
477               }
478               ret << "(";
479               ret << (*iter).first.format() << "*" << (*iter).second.first;
480               if ((*iter).second.second) {
481                   ret << ", will round to TOP or BOTTOM";
482               }
483               ret << ")";
484           }
485           foundType = true;
486       }
487       if (isDelta()) {
488           if (!foundType) {
489             ret << target.format() << "+" << delta;
490           } else {
491             ret << "+" << delta;
492           }
493       }
494    }
495    if (isTopBottom()) {
496     ret << ", will round to TOP or BOTTOM";
497    }
498    ret << "]";
499    return ret.str();
500 }
501
502 std::string StackAnalysis::SummaryFunc::format() const {
503    stringstream ret;
504    for (TransferSet::const_iterator iter = accumFuncs.begin();
505         iter != accumFuncs.end(); ++iter) {
506       ret << iter->second.format() << endl;
507    }
508    return ret.str();
509 }
510
511
512 void StackAnalysis::findDefinedHeights(ParseAPI::Block* b, Address addr, std::vector<std::pair<Absloc, Height> >& heights)
513 {
514   if (func == NULL) return;
515
516   if (!intervals_) {
517     // Check annotation
518     func->getAnnotation(intervals_, Stack_Anno);
519   }
520   if (!intervals_) {
521     // Analyze?
522     if (!analyze()) return;
523   }
524   assert(intervals_);
525   for(AbslocState::iterator i = (*intervals_)[b][addr].begin();
526       i != (*intervals_)[b][addr].end();
527       ++i)
528   {
529     if(i->second.isTop())
530     {
531       continue;
532     }
533     stackanalysis_printf("\t\tAdding %s:%s to defined heights at 0x%lx\n",
534                          i->first.format().c_str(),
535                          i->second.format().c_str(),
536                          addr);
537
538     heights.push_back(*i);
539   }
540 }
541
542 StackAnalysis::Height StackAnalysis::find(Block *b, Address addr, Absloc loc) {
543
544   Height ret; // Defaults to "top"
545
546   if (func == NULL) return ret;
547   
548   if (!intervals_) {
549     // Check annotation
550     func->getAnnotation(intervals_, Stack_Anno);
551   }
552   if (!intervals_) {
553     // Analyze?
554     if (!analyze()) return Height();
555   }
556   assert(intervals_);
557
558   //(*intervals_)[b].find(addr, state);
559   //  ret = (*intervals_)[b][addr][reg];
560   Intervals::iterator iter = intervals_->find(b);
561   if (iter == intervals_->end()) {
562           // How do we return "you stupid idiot"?
563
564           return Height::bottom;
565   }
566
567   StateIntervals &sintervals = iter->second;
568   if (sintervals.empty()) {
569           return Height::bottom;
570   }
571   //Find the last instruction that is <= addr
572   StateIntervals::iterator i = sintervals.lower_bound(addr);
573   if ((i == sintervals.end() && !sintervals.empty()) || 
574       (i->first != addr && i != sintervals.begin())) {
575       i--;
576   }
577   if (i == sintervals.end()) return Height::bottom;
578
579   ret = i->second[loc];
580
581   if (ret.isTop()) {
582      return Height::bottom;
583   }
584   return ret;
585 }
586
587 StackAnalysis::Height StackAnalysis::findSP(Block *b, Address addr) {
588    return find(b, addr, sp());
589 }
590
591 StackAnalysis::Height StackAnalysis::findFP(Block *b, Address addr) {
592    return find(b, addr, fp());
593 }
594
595 std::ostream &operator<<(std::ostream &os, const Dyninst::StackAnalysis::Height &h) {
596   os << "STACK_SLOT[" << h.format() << "]";
597   return os;
598 }
599
600 ///////////////////
601 // Insn effect fragments
602 ///////////////////
603 void StackAnalysis::handleXor(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
604    std::vector<Operand> operands;
605    insn->getOperands(operands);
606    assert(operands.size() == 2);
607
608    // Handle the case where a register is being zeroed out.
609    // We recognize such cases as follows:
610    //   1. Exactly one register is both read and written
611    //   2. The Expression tree for each operand consists of a single leaf node
612    std::set<RegisterAST::Ptr> readSet;
613    std::set<RegisterAST::Ptr> writtenSet;
614    operands[0].getWriteSet(writtenSet);
615    operands[1].getReadSet(readSet);
616
617    std::vector<Expression::Ptr> children0;
618    std::vector<Expression::Ptr> children1;
619    operands[0].getValue()->getChildren(children0);
620    operands[1].getValue()->getChildren(children1);
621
622    if (readSet.size() == 1 && writtenSet.size() == 1 &&
623       (*readSet.begin())->getID() == (*writtenSet.begin())->getID() &&
624       children0.size() == 0 && children1.size() == 0) {
625       stackanalysis_printf("\t\t\t Register zeroing detected\n");
626       Absloc loc((*writtenSet.begin())->getID());
627       xferFuncs.push_back(TransferFunc::absFunc(loc, 0));
628    } else {
629       handleDefault(insn, xferFuncs);
630    }
631 }
632
633
634 void StackAnalysis::handlePushPop(Instruction::Ptr insn, int sign,
635    TransferFuncs &xferFuncs) {
636
637    long delta = 0;
638    Operand arg = insn->getOperand(0);
639    // Why was this here? bernat, 12JAN11
640    if (arg.getValue()->eval().defined) {
641       delta = sign * word_size;
642       stackanalysis_printf(
643          "\t\t\t Stack height changed by evaluated push/pop: %lx\n", delta);
644    }
645    else {
646       delta = sign * arg.getValue()->size();
647       //cerr << "Odd case: set delta to " << hex << delta << dec << " for instruction " << insn->format() << endl;
648       stackanalysis_printf(
649          "\t\t\t Stack height changed by unevalled push/pop: %lx\n", delta);
650    }
651    //   delta = sign *arg.getValue()->size();
652    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
653
654    // Let's get whatever was popped (if it was)
655    if (insn->getOperation().getID() == e_pop &&
656        !insn->writesMemory()) {
657       MachRegister reg = sp();
658
659       std::set<RegisterAST::Ptr> written;
660       insn->getWriteSet(written);
661       for (std::set<RegisterAST::Ptr>::iterator iter = written.begin(); 
662            iter != written.end(); ++iter) {
663          if ((*iter)->getID() != sp()) reg = (*iter)->getID();
664       }
665       xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(reg)));
666    }
667 }
668
669 void StackAnalysis::handleReturn(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
670    long delta = 0;
671    std::vector<Operand> operands;
672    insn->getOperands(operands);
673    if (operands.size() == 0) {
674       delta = word_size;
675    }
676    else if (operands.size() == 1) {
677       // Ret immediate
678       Result imm = operands[0].getValue()->eval();
679       if (imm.defined) {
680          delta = word_size + imm.convert<int>();
681       }
682       else {
683          stackanalysis_printf("\t\t\t Stack height changed by return: bottom\n");
684          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(sp())));
685       }
686    }
687    stackanalysis_printf("\t\t\t Stack height changed by return: %lx\n", delta);
688    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
689 }
690
691 void StackAnalysis::handleAddSub(Instruction::Ptr insn, int sign, TransferFuncs &xferFuncs) {
692    // add reg, mem is ignored
693    // add mem, reg bottoms reg
694    if (insn->writesMemory()) return;
695    if (insn->readsMemory()) {
696       handleDefault(insn, xferFuncs);
697       return;
698    }
699
700    std::set<RegisterAST::Ptr> readSet;
701    insn->getOperand(0).getReadSet(readSet);
702    if (readSet.size() != 1) {
703       fprintf(stderr, "readSet != 1\n");
704       handleDefault(insn, xferFuncs);
705       return;
706    }
707
708    // Add/subtract are op0 += (or -=) op1
709    Operand arg = insn->getOperand(1);
710    Result res = arg.getValue()->eval();
711    if (res.defined) {
712       long delta = 0;
713       // Size is in bytes...
714       switch(res.size()) {
715       case 1:
716          delta = sign * res.convert<int8_t>();
717          break;
718       case 2:
719          delta = sign * res.convert<int16_t>();
720          break;
721       case 4:
722          delta = sign * res.convert<int32_t>();
723          break;
724       case 8:
725          delta = sign * res.convert<int64_t>();
726          break;
727       default:
728          assert(0);
729       }
730       stackanalysis_printf(
731          "\t\t\t Stack height changed by evalled add/sub: %lx\n", delta);
732       Absloc loc((*(readSet.begin()))->getID());
733       xferFuncs.push_back(TransferFunc::deltaFunc(loc, delta));
734    }
735    else {
736       handleDefault(insn, xferFuncs);
737    }
738
739    return;
740 }
741
742 void StackAnalysis::handleLEA(Instruction::Ptr insn,
743    TransferFuncs &xferFuncs) {
744
745    // LEA has a pattern of:
746    // op0: target register
747    // op1: add(source, <const>)
748    // 
749    // Since we don't know what the value in source is, we can't do this a
750    // priori. Instead, TRANSFER FUNCTION!
751    
752    stackanalysis_printf("\t\t\t handleLEA, insn = %s\n",
753       insn->format().c_str());
754
755    std::set<RegisterAST::Ptr> readSet;
756    std::set<RegisterAST::Ptr> writtenSet;
757    insn->getOperand(0).getWriteSet(writtenSet); assert(writtenSet.size() == 1);
758    insn->getOperand(1).getReadSet(readSet); //assert(readSet.size() == 1);
759    MachRegister written = (*writtenSet.begin())->getID();
760
761    TransferFunc lea;
762
763    // conservative...
764    if (readSet.size() != 1) {
765       if (readSet.size() != 2) {
766          // This shouldn't happen
767          stackanalysis_printf(
768             "\t\t\tUnexpected LEA case. Setting %s = BOTTOM\n",
769             written.name().c_str());
770          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(written)));
771          return;
772       }
773
774       MachRegister base, index;
775       long scale = -1;
776
777       InstructionAPI::Operand srcOperand = insn->getOperand(1);
778       InstructionAPI::Expression::Ptr srcExpr = srcOperand.getValue();
779
780       std::vector<InstructionAPI::Expression::Ptr> children;
781       srcExpr->getChildren(children);
782
783       InstructionAPI::Expression::Ptr baseExpr, scaleIndexExpr, deltaExpr;
784       bool foundDelta = false;
785       while (1) {
786          if (typeid(*(children[0])) == typeid(InstructionAPI::RegisterAST)) {
787             baseExpr = children[0];
788             scaleIndexExpr = children[1];
789             if (typeid(*scaleIndexExpr) !=
790                typeid(InstructionAPI::BinaryFunction)) {
791
792                stackanalysis_printf(
793                   "\t\t\tUnhandled LEA - scale or index missing. "
794                   "Setting %s = BOTTOM\n", written.name().c_str());
795                Absloc loc(written);
796                xferFuncs.push_back(TransferFunc::bottomFunc(loc));
797                return;
798             }
799             break;
800          }
801
802          // If there's a delta, then the SIB is inside a dereference,
803          // and we need to get the child of the deref
804          deltaExpr = children[1];
805          if (typeid(*deltaExpr) != typeid(InstructionAPI::Immediate)) {
806             stackanalysis_printf("\t\t\tUnhandled LEA - non-immediate delta. "
807                "Setting %s = BOTTOM\n", written.name().c_str());
808             xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(written)));
809             return;
810          }
811          foundDelta = true;
812          InstructionAPI::Expression::Ptr tmp = children[0];
813          children.clear();
814          tmp->getChildren(children);
815       }
816
817       // Get the base register
818       base = (boost::dynamic_pointer_cast<InstructionAPI::RegisterAST>(
819          baseExpr))->getID();
820
821       // Extract the index and scale
822       children.clear();
823       scaleIndexExpr->getChildren(children);
824       InstructionAPI::Expression::Ptr scaleExpr, indexExpr;
825       indexExpr = children[0];
826       if (typeid(*indexExpr) != typeid(InstructionAPI::RegisterAST)) {
827          stackanalysis_printf(
828             "Unhandled LEA - non-register index. Setting %s = BOTTOM\n",
829             written.name().c_str());
830          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(written)));
831          return;
832       }
833       scaleExpr = children[1];
834       if (typeid(*scaleExpr) != typeid(InstructionAPI::Immediate)) {
835          stackanalysis_printf(
836             "Unhandled LEA - non-immediate scale. Setting %s = BOTTOM\n",
837             written.name().c_str());
838          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(written)));
839          return;
840       }
841
842       index = (boost::dynamic_pointer_cast<InstructionAPI::RegisterAST>(
843          indexExpr))->getID();
844       scale = (boost::dynamic_pointer_cast<InstructionAPI::Immediate>(
845          scaleExpr))->eval().convert<long>();
846
847       long delta = 0;
848       if (foundDelta) {
849          Result deltaRes = (boost::dynamic_pointer_cast<InstructionAPI::
850             Immediate>(deltaExpr))->eval();
851          switch(deltaRes.size()) {
852             case 1:
853                delta = (long)deltaRes.convert<int8_t>();
854                break;
855             case 2:
856                delta = (long)deltaRes.convert<int16_t>();
857                break;
858             case 4:
859                delta = (long)deltaRes.convert<int32_t>();
860                break;
861             case 8:
862                delta = (long)deltaRes.convert<int64_t>();
863                break;
864             default:
865                assert(0);
866          }
867       }
868
869       if (!base.isValid() || !index.isValid() || (scale==-1)) {
870          stackanalysis_printf("Misunderstood LEA. Setting %s = BOTTOM\n",
871             written.name().c_str());
872          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(written)));
873          return;
874       }
875
876       // Consolidate when possible
877       if (base == index) {
878          base = MachRegister();
879          scale++;
880       }
881
882       std::map<Absloc,std::pair<long,bool> > fromRegs;
883       if (base.isValid()) {
884          fromRegs.insert(make_pair(Absloc(base), make_pair(1, false)));
885       }
886       fromRegs.insert(make_pair(Absloc(index), make_pair(scale, false)));
887       lea = TransferFunc::sibFunc(fromRegs, delta, Absloc(written));
888       xferFuncs.push_back(lea);
889       return;
890    } else {
891       Absloc readloc((*(readSet.begin()))->getID());
892       Absloc writeloc(written);
893       lea = TransferFunc::aliasFunc(readloc, writeloc);
894    }
895
896    // Non-SIB LEA also performs computation, so we need to determine and set
897    // the delta parameter.
898    MachRegister reg;
899    long scale = 1;
900    long delta = 0;
901    InstructionAPI::Operand srcOperand = insn->getOperand(1);
902    InstructionAPI::Expression::Ptr srcExpr = srcOperand.getValue();
903
904    stackanalysis_printf("\t\t\t\t srcOperand = %s\n",
905       srcExpr->format().c_str());
906
907    std::vector<InstructionAPI::Expression::Ptr> children;
908    srcExpr->getChildren(children);
909    stackanalysis_printf("\t\t\t\t srcOperand # children = %d\n",
910       children.size());
911
912    InstructionAPI::Expression::Ptr regExpr, scaleExpr, deltaExpr;
913    bool foundScale = false;
914    bool foundDelta = false;
915
916    if (children.size()) {
917       for (auto iter = children.begin(); iter != children.end(); ++iter) {
918          InstructionAPI::Expression::Ptr child = *iter;
919          if (typeid(*child) == typeid(InstructionAPI::Immediate)) {
920             deltaExpr = child;
921             foundDelta = true;
922          } else if (typeid(*child) == typeid(InstructionAPI::RegisterAST)) {
923             regExpr = child;
924          } else if (typeid(*child) == typeid(InstructionAPI::BinaryFunction)) {
925             std::vector<InstructionAPI::Expression::Ptr> subchildren;
926             child->getChildren(subchildren);
927             regExpr = subchildren[0];
928             if (typeid(*regExpr) != typeid(InstructionAPI::RegisterAST)) {
929                stackanalysis_printf("Unhandled LEA - non-SIB non-register "
930                   "index. Setting %s = BOTTOM\n", written.name().c_str());
931                Absloc loc(written);
932                xferFuncs.push_back(TransferFunc::bottomFunc(loc));
933                return;
934             }
935             scaleExpr = subchildren[1];
936             if (typeid(*scaleExpr) != typeid(InstructionAPI::Immediate)) {
937                stackanalysis_printf("Unhandled LEA - non-SIB non-immediate "
938                   "scale. Setting %s = BOTTOM\n", written.name().c_str());
939                Absloc loc(written);
940                xferFuncs.push_back(TransferFunc::bottomFunc(loc));
941                return;
942             }
943             foundScale = true;
944          }
945       }
946    } else {
947       regExpr = srcExpr;
948    }
949    reg = (boost::dynamic_pointer_cast<InstructionAPI::RegisterAST>(regExpr))->
950       getID();
951
952    if (foundScale) {
953       scale = (boost::dynamic_pointer_cast<InstructionAPI::Immediate>(
954          scaleExpr))->eval().convert<long>();
955    }
956
957    if (foundDelta) {
958       Result deltaRes = (boost::dynamic_pointer_cast<InstructionAPI::
959          Immediate>(deltaExpr))->eval();
960       switch(deltaRes.size()) {
961          case 1:
962             delta = (long)deltaRes.convert<int8_t>();
963             break;
964          case 2:
965             delta = (long)deltaRes.convert<int16_t>();
966             break;
967          case 4:
968             delta = (long)deltaRes.convert<int32_t>();
969             break;
970          case 8:
971             delta = (long)deltaRes.convert<int64_t>();
972             break;
973          default:
974             assert(0);
975       }
976    }
977
978    if (!foundScale) {
979       lea.delta = delta;
980    } else {
981       std::map<Absloc,std::pair<long, bool> > fromRegs;
982       fromRegs.insert(make_pair(Absloc(reg), make_pair(scale, false)));
983       Absloc loc(written);
984       lea = TransferFunc::sibFunc(fromRegs, delta, loc);
985    }
986
987    xferFuncs.push_back(lea);
988    return;
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::topFunc(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::topFunc(Absloc r) {
1591    return absFunc(r, uninitialized, false);
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() && !isSIB();
1601 }
1602
1603 bool StackAnalysis::TransferFunc::isTop() const {
1604    return (!isDelta() && !isAbs() && !isAlias() && !isSIB());
1605 }
1606
1607 bool StackAnalysis::TransferFunc::isAlias() const {
1608    return from.isValid();
1609 }
1610
1611 bool StackAnalysis::TransferFunc::isAbs() const {
1612    return (abs != uninitialized && abs != notUnique);
1613 }
1614
1615 bool StackAnalysis::TransferFunc::isDelta() const {
1616    return (delta != 0);
1617 }
1618
1619 bool StackAnalysis::TransferFunc::isSIB() const {
1620     return (fromRegs.size() > 0);
1621 }
1622
1623
1624
1625 // Destructive update of the input map. Assumes inputs are absolute,
1626 // uninitalized, or bottom; no deltas.
1627 StackAnalysis::Height StackAnalysis::TransferFunc::apply(
1628    const AbslocState &inputs) const {
1629
1630    assert(target.isValid());
1631    // Bottom stomps everything
1632    if (isBottom()) {
1633       return Height::bottom;
1634    }
1635
1636    AbslocState::const_iterator iter = inputs.find(target);
1637    Height input;
1638    if (iter != inputs.end()) {
1639       input = iter->second;
1640    }
1641    else {
1642       input = Height::top;
1643    }
1644
1645    bool isTopBottomOrig = isTopBottom();
1646
1647    if (isSIB()) {
1648       input = Height::top; // SIB overwrites, so start at TOP
1649       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
1650          Absloc curLoc = (*iter).first;
1651          long curScale = (*iter).second.first;
1652          bool curTopBottom = (*iter).second.second;
1653          auto findReg = inputs.find(curLoc);
1654          Height regInput;
1655          if (findReg == inputs.end()) {
1656             regInput = Height::top;
1657          } else {
1658             regInput = findReg->second;
1659          }
1660
1661          if (regInput == Height::top) {
1662             // Ignore--has no effect on ouput
1663          } else if (regInput == Height::bottom) {
1664             // Must bottom everything
1665             input = Height::bottom;
1666             break;
1667          } else {
1668             if (curScale != 1) {
1669                // Must bottom
1670                input = Height::bottom;
1671                break;
1672             } else {
1673                if (input != Height::top) {
1674                   // Must bottom--cannot add stack heights
1675                   input = Height::bottom;
1676                   break;
1677                } else {
1678                   if (curTopBottom) {
1679                      input = Height::bottom;
1680                   } else {
1681                      // Finally! We can add!
1682                      input += regInput;
1683                   }
1684                }
1685             }
1686          }
1687       }
1688    }
1689
1690    if (isAbs()) {
1691       // We cannot be an alias, as the absolute removes that. 
1692       assert(!isAlias());
1693       // Apply the absolute
1694       // NOTE: an absolute is not a stack height, set input to top
1695       //input = abs;
1696       input = Height::top;
1697    }
1698    if (isAlias()) {
1699       // Cannot be absolute
1700       assert(!isAbs());
1701       // Copy the input value from whatever we're an alias of.
1702       AbslocState::const_iterator iter2 = inputs.find(from);
1703       if (iter2 != inputs.end()) input = iter2->second;
1704       else input = Height::top;
1705    }
1706    if (isDelta()) {
1707       input += delta;
1708    }
1709    if (isTopBottomOrig) {
1710       if (!input.isTop()) {
1711          input = Height::bottom;
1712       }
1713    }
1714    return input;
1715 }
1716
1717 // Accumulation to the input map. This is intended to create a summary, so we create
1718 // something that can take further input.
1719 void StackAnalysis::TransferFunc::accumulate(std::map<Absloc, TransferFunc> &inputs ) {
1720    TransferFunc &input = inputs[target];
1721    if (input.target.isValid()) assert(input.target == target);
1722    input.target = target; // Default constructed TransferFuncs won't have this
1723    assert(target.isValid());
1724
1725    // Bottom stomps everything
1726    if (isBottom()) {
1727       input = bottomFunc(target);
1728       return;
1729    }
1730    bool isTopBottomOrig = isTopBottom();
1731    if (!input.isTopBottom()) {
1732       input.topBottom = isTopBottomOrig;
1733    }
1734    // Absolutes override everything else
1735    if (isAbs()) {
1736       input = absFunc(target, abs, isTopBottomOrig);
1737       return;
1738    }
1739    if (isSIB()) {
1740       std::map<Absloc, std::pair<long,bool> > newFromRegs;
1741       long newDelta = delta;
1742
1743       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
1744          Absloc fromLocOrig = (*iter).first;
1745          long scaleOrig = (*iter).second.first;
1746
1747          auto findLoc = inputs.find(fromLocOrig);
1748          if (findLoc == inputs.end()) {
1749             // Easy case
1750             auto found = newFromRegs.find(fromLocOrig);
1751             if (found == newFromRegs.end()) {
1752                newFromRegs.insert(make_pair(fromLocOrig,
1753                   make_pair(scaleOrig, false)));
1754             } else {
1755                newFromRegs[fromLocOrig].first += scaleOrig;
1756             }
1757          } else {
1758             TransferFunc fromRegFunc = findLoc->second;
1759             if (fromRegFunc.isAbs()) {
1760                newDelta += fromRegFunc.abs*scaleOrig;
1761
1762                // If we're processing the last source register,
1763                // and we haven't added anything to the new register set, this
1764                // must be a group of abs
1765                auto tmp = iter;
1766                tmp++;
1767                if (tmp == fromRegs.end()) {
1768                   if (newFromRegs.size() == 0) {
1769                      input = absFunc(target, newDelta);
1770                      return;
1771                   }
1772                }
1773             }
1774             if (fromRegFunc.isSIB()) {
1775                // Replace registers and update scales
1776                for (auto regIter = fromRegFunc.fromRegs.begin();
1777                   regIter != fromRegFunc.fromRegs.end(); ++regIter) {
1778                   Absloc replaceLoc = regIter->first;
1779                   long replaceScale = regIter->second.first;
1780                   long replaceTopBottom = regIter->second.second;
1781                   long newScale = replaceScale*scaleOrig;
1782
1783                   // If this register already exists in the map, we need to
1784                   // add, rather than overwrite!
1785                   auto found = newFromRegs.find(replaceLoc);
1786                   if (found == newFromRegs.end()) {
1787                      newFromRegs.insert(make_pair(replaceLoc,
1788                         make_pair(newScale, replaceTopBottom)));
1789                   } else {
1790                      newFromRegs[replaceLoc].first += newScale;
1791                      newFromRegs[replaceLoc].second += replaceTopBottom;
1792                   }
1793                }
1794             }
1795             if (fromRegFunc.isBottom()) {
1796                // Any bottom'd input bottoms the output
1797                input = bottomFunc(target);
1798                return;
1799             }
1800             if (fromRegFunc.isAlias()) {
1801                // Replace fromRegOrig with fromRegFunc.from
1802                auto found = newFromRegs.find(fromRegFunc.from);
1803                if (found == newFromRegs.end()) {
1804                   newFromRegs.insert(make_pair(fromRegFunc.from,
1805                      make_pair(scaleOrig,fromRegFunc.isTopBottom())));
1806                } else {
1807                   newFromRegs[fromRegFunc.from].first += scaleOrig;
1808                }
1809             }
1810             if (fromRegFunc.isDelta()) {
1811                newDelta += fromRegFunc.delta*scaleOrig;
1812                if (!fromRegFunc.isAlias() && !fromRegFunc.isSIB() &&
1813                   !fromRegFunc.isAbs()) {
1814                   // Add the register back in...
1815                   auto found = newFromRegs.find(fromLocOrig);
1816                   if (found == newFromRegs.end()) {
1817                      newFromRegs.insert(make_pair(fromLocOrig,
1818                         make_pair(scaleOrig,false)));
1819                   } else {
1820                      newFromRegs[fromLocOrig].first += scaleOrig;
1821                   }
1822                }
1823             }
1824             // This is the default constructed target when the target didn't
1825             // already exist--need to explicitly update...
1826             if (fromRegFunc.isTop()) {
1827                auto found = newFromRegs.find(fromLocOrig);
1828                if (found == newFromRegs.end()) {
1829                   newFromRegs.insert(make_pair(fromLocOrig,
1830                      make_pair(scaleOrig,false)));
1831                } else {
1832                   newFromRegs[fromLocOrig].first += scaleOrig;
1833                }
1834             }
1835          }
1836       }
1837       input = sibFunc(newFromRegs, newDelta, target);
1838       input.topBottom = isTopBottomOrig;
1839       return;
1840    }
1841
1842    // Aliases can be tricky
1843    // apply alias logic only if registers are different
1844    if (isAlias() && target != from) {
1845       // We need to record that we want to take the inflow height
1846       // of a different register. 
1847       // Don't do an inputs[from] as that creates
1848       std::map<Absloc, TransferFunc>::iterator iter = inputs.find(from);
1849       if (iter == inputs.end()) {
1850          // Aliasing to something we haven't seen yet; easy
1851          input = *this;
1852          input.topBottom = isTopBottomOrig;
1853          return;
1854       }
1855
1856       TransferFunc &alias = iter->second;
1857
1858       if (alias.isAbs()) {
1859          // Easy; we reset the height, so we don't care about the inflow height.
1860          // This might be a delta from that absolute, but all that we care about is that
1861          // we ignore any inflow. 
1862          assert(!alias.isAlias());
1863          input = absFunc(input.target, alias.abs);
1864          input.topBottom = isTopBottomOrig || alias.isTopBottom(); // If we got an abs from an isTopBottom, this also needs to be set
1865          assert(input.target.isValid());
1866
1867          // if the input was also a delta, apply this
1868          if (isDelta()) {
1869             input.delta += delta;
1870          }
1871          return;
1872       }
1873       if (alias.isAlias()) {
1874          // Transitivity! We cut that short.
1875          // Again, it might be a delta since the alias, which we'll copy over. It cannot
1876          // be an absolute because that will remove the alias (and vice versa).
1877          assert(!alias.isAbs());
1878          input = alias;
1879          input.target = target;
1880          input.topBottom = isTopBottomOrig || alias.isTopBottom();
1881          assert(input.target.isValid());
1882
1883          // if the input was also a delta, apply this also 
1884          if (isDelta()) {
1885             input.delta += delta;
1886          }
1887
1888          return;
1889       }
1890       if (alias.isSIB()) {
1891          input = alias;
1892          input.target = target;
1893          input.topBottom = isTopBottomOrig;
1894
1895          if (isDelta()) {
1896              input.delta += delta;
1897          }
1898
1899          return;
1900       }
1901
1902       // without bottom we mess up in the default case.
1903       if (alias.isBottom()) {
1904          input = bottomFunc(target);
1905          return;
1906       }
1907
1908       // add top?
1909
1910       // Default case: record the alias, zero out everything else, copy over the delta
1911       // if it's defined.
1912       //input.target is defined
1913       input.from = alias.target;
1914       input.abs = uninitialized;
1915       if (alias.isDelta()) {
1916          input.delta = alias.delta;
1917       }
1918       else {
1919          input.delta = 0;
1920       }
1921       input.topBottom = isTopBottomOrig || alias.isTopBottom(); // pass source tb
1922       input.fromRegs.clear();
1923
1924       // if the input was also a delta, apply this also 
1925       if (isDelta()) {
1926          input.delta += delta;
1927       }
1928
1929       return;
1930    }
1931
1932    if (isDelta()) {
1933       // A delta can apply cleanly to anything, since Height += handles top/bottom
1934       input.delta += delta;
1935       return;
1936    }
1937    // Reachable because isDelta returns false for delta = 0; this is OK
1938    return;
1939 }
1940
1941
1942 void StackAnalysis::SummaryFunc::apply(const AbslocState &in,
1943    AbslocState &out) const {
1944
1945    // Copy all the elements we don't have xfer funcs for.
1946    out = in;
1947
1948    // Apply in parallel since all summary funcs are from the start of the block
1949    for (TransferSet::const_iterator iter = accumFuncs.begin();
1950       iter != accumFuncs.end(); ++iter) {
1951       assert(iter->first.isValid());
1952       out[iter->first] = iter->second.apply(in);
1953    }
1954 }
1955
1956
1957 void StackAnalysis::SummaryFunc::add(TransferFuncs &xferFuncs) {
1958    // We need to update our register->xferFunc map
1959    // with the effects of each of the transferFuncs. 
1960    
1961    for (TransferFuncs::iterator iter = xferFuncs.begin(); 
1962         iter != xferFuncs.end(); ++iter) {
1963       TransferFunc &func = *iter;
1964
1965       func.accumulate(accumFuncs);
1966       validate();
1967    }
1968
1969 }
1970
1971 void StackAnalysis::SummaryFunc::validate() const {
1972    for (TransferSet::const_iterator iter = accumFuncs.begin(); 
1973         iter != accumFuncs.end(); ++iter)
1974    {
1975       const TransferFunc &func = iter->second;
1976       assert(func.target.isValid());
1977       if (func.isAlias()) assert(!func.isAbs());
1978       if (func.isAbs()) assert(!func.isAlias());
1979       if (func.isBottom()) assert(!func.isAlias());
1980    }
1981 }
1982
1983 MachRegister StackAnalysis::sp() { 
1984    return MachRegister::getStackPointer(func->isrc()->getArch());
1985 }
1986
1987 MachRegister StackAnalysis::fp() { 
1988    return MachRegister::getFramePointer(func->isrc()->getArch());
1989 }
1990
1991 std::string StackAnalysis::format(const AbslocState &input) const {
1992    std::stringstream ret;
1993    for (AbslocState::const_iterator iter = input.begin();
1994       iter != input.end(); ++iter) {
1995       ret << iter->first.format() << " := " << iter->second.format() << ", ";
1996    }
1997    return ret.str();
1998 }