Track the relationship between base and subregisters.
[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 "stackanalysis.h"
32
33 #include <boost/bind.hpp>
34 #include <queue>
35 #include <vector>
36
37 #include "instructionAPI/h/BinaryFunction.h"
38 #include "instructionAPI/h/Dereference.h"
39 #include "instructionAPI/h/Expression.h"
40 #include "instructionAPI/h/Immediate.h"
41 #include "instructionAPI/h/InstructionDecoder.h"
42 #include "instructionAPI/h/Instruction.h"
43 #include "instructionAPI/h/Register.h"
44 #include "instructionAPI/h/Result.h"
45 #include "parseAPI/h/CFG.h"
46 #include "parseAPI/h/CodeObject.h"
47
48 #include "ABI.h"
49 #include "Annotatable.h"
50 #include "debug_dataflow.h"
51
52 using namespace std;
53 using namespace Dyninst;
54 using namespace InstructionAPI;
55 using namespace Dyninst::ParseAPI;
56
57 const StackAnalysis::Height StackAnalysis::Height::bottom(
58    StackAnalysis::Height::notUnique, StackAnalysis::Height::BOTTOM);
59 const StackAnalysis::Height StackAnalysis::Height::top(
60    StackAnalysis::Height::uninitialized, StackAnalysis::Height::TOP);
61
62 AnnotationClass<StackAnalysis::Intervals>
63    Stack_Anno_Intervals(std::string("Stack_Anno_Intervals"));
64 AnnotationClass<StackAnalysis::BlockEffects>
65    Stack_Anno_Block_Effects(std::string("Stack_Anno_Block_Effects"));
66 AnnotationClass<StackAnalysis::InstructionEffects>
67    Stack_Anno_Insn_Effects(std::string("Stack_Anno_Insn_Effects"));
68
69 template class std::list<Dyninst::StackAnalysis::TransferFunc*>;
70 template class std::map<Dyninst::Absloc, Dyninst::StackAnalysis::Height>;
71 template class std::vector<Dyninst::InstructionAPI::Instruction::Ptr>;
72 //
73 // Concepts:
74 //
75 // There are three terms we throw around:
76 // 
77 // Stack height: the size of the stack; (cur_stack_ptr - func_start_stack_ptr)
78 // Stack delta: the difference in the size of the stack over the execution of
79 //   a region of code (basic block here). (block_end_stack_ptr -
80 //   block_start_stack_ptr)
81 // Stack clean: the amount the callee function shifts the stack. This is an x86
82 //   idiom. On x86 the caller pushes arguments onto the stack (and thus shifts
83 //   the stack). Normally the caller also cleans the stack (that is, removes
84 //   arguments). However, some callee functions perform this cleaning
85 //   themselves. We need to account for this in our analysis, which otherwise
86 //   assumes that callee functions don't alter the stack.
87
88
89 bool StackAnalysis::analyze() {
90    df_init_debug();
91
92    genInsnEffects();
93
94    stackanalysis_printf("\tPerforming fixpoint analysis\n");
95    fixpoint();
96    stackanalysis_printf("\tCreating SP interval tree\n");
97    summarize();
98
99    func->addAnnotation(intervals_, Stack_Anno_Intervals);
100
101    if (df_debug_stackanalysis) {
102       debug();
103    }
104
105    stackanalysis_printf("Finished stack analysis for function %s\n",
106       func->name().c_str());
107
108    return true;
109 }
110
111
112 bool StackAnalysis::genInsnEffects() {
113    // Check if we've already done this work
114    if (blockEffects != NULL && insnEffects != NULL) return true;
115    func->getAnnotation(blockEffects, Stack_Anno_Block_Effects);
116    func->getAnnotation(insnEffects, Stack_Anno_Insn_Effects);
117    if (blockEffects != NULL && insnEffects != NULL) return true;
118
119    blockEffects = new BlockEffects();
120    insnEffects = new InstructionEffects();
121
122    stackanalysis_printf("Beginning insn effect generation for function %s\n",
123       func->name().c_str());
124
125    // Initial analysis to get register stack heights
126    stackanalysis_printf("\tSummarizing intermediate block effects\n");
127    summarizeBlocks();
128    stackanalysis_printf("\tPerforming intermediate fixpoint analysis\n");
129    fixpoint();
130    stackanalysis_printf("\tCreating intermediate SP interval tree\n");
131    summarize();
132
133    // Clear mappings
134    blockEffects->clear();
135    insnEffects->clear();
136    blockInputs.clear();
137    blockOutputs.clear();
138
139    // Generate final block effects with stack slot tracking
140    stackanalysis_printf("\tGenerating final block effects\n");
141    summarizeBlocks();
142
143    // Annotate insnEffects and blockEffects to avoid rework
144    func->addAnnotation(blockEffects, Stack_Anno_Block_Effects);
145    func->addAnnotation(insnEffects, Stack_Anno_Insn_Effects);
146
147    stackanalysis_printf("Finished insn effect generation for function %s\n",
148       func->name().c_str());
149
150    return true;
151 }
152
153 typedef std::vector<std::pair<Instruction::Ptr, Offset> > InsnVec;
154 static void getInsnInstances(Block *block, InsnVec &insns) {
155    Offset off = block->start();
156    const unsigned char *ptr = (const unsigned char *)
157       block->region()->getPtrToInstruction(off);
158    if (ptr == NULL) return;
159    InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
160    while (off < block->end()) {
161       insns.push_back(std::make_pair(d.decode(), off));
162       off += insns.back().first->size();
163    }
164 }
165
166
167 // We want to create a transfer function for the block as a whole. This will
168 // allow us to perform our fixpoint calculation over blocks (thus, O(B^2))
169 // rather than instructions (thus, O(I^2)).
170 //
171 // Handling the stack height is straightforward. We also accumulate region
172 // changes in terms of a stack of Region objects.
173 void StackAnalysis::summarizeBlocks() {
174    Function::blocklist bs(func->blocks());
175    for (auto bit = bs.begin(); bit != bs.end(); ++bit) {
176       Block *block = *bit;
177       // Accumulators. They have the following behavior:
178       //
179       // New region: add to the end of the regions list
180       // Offset to stack pointer: accumulate to delta.
181       // Setting the stack pointer: zero delta, set set_value.
182
183       SummaryFunc &bFunc = (*blockEffects)[block];
184
185       stackanalysis_printf("\t Block starting at 0x%lx: %s\n", block->start(),
186          bFunc.format().c_str());
187       InsnVec instances;
188       getInsnInstances(block, instances);
189
190       for (unsigned j = 0; j < instances.size(); j++) {
191          InstructionAPI::Instruction::Ptr insn = instances[j].first;
192          Offset &off = instances[j].second;
193
194          // Fills in insnEffects[off]
195          TransferFuncs &xferFuncs = (*insnEffects)[block][off];
196
197          computeInsnEffects(block, insn, off, xferFuncs);
198          bFunc.add(xferFuncs);
199
200          stackanalysis_printf("\t\t\t At 0x%lx:  %s\n", off,
201             bFunc.format().c_str());
202       }
203    stackanalysis_printf("\t Block summary for 0x%lx: %s\n", block->start(),
204       bFunc.format().c_str());
205    }
206 }
207
208 struct intra_nosink : public ParseAPI::EdgePredicate {
209    virtual bool operator()(Edge* e) {
210       static Intraproc i;
211       static NoSinkPredicate n;
212       return i(e) && n(e);
213    }
214 };
215
216 void add_target(std::queue<Block*>& worklist, Edge* e) {
217    worklist.push(e->trg());
218 }
219
220 void StackAnalysis::fixpoint() {
221    intra_nosink epred2;
222
223    std::queue<Block *> worklist;
224    worklist.push(func->entry());
225
226    bool firstBlock = true;
227    while (!worklist.empty()) {
228       Block *block = worklist.front();
229       worklist.pop();
230       stackanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n",
231          block->start());
232
233       // Step 1: calculate the meet over the heights of all incoming
234       // intraprocedural blocks.
235       AbslocState input;
236       if (firstBlock) {
237          createEntryInput(input);
238          stackanalysis_printf("\t Primed initial block\n");
239       } else {
240          stackanalysis_printf("\t Calculating meet with block [%x-%x]\n",
241             block->start(), block->lastInsnAddr());
242          meetInputs(block, blockInputs[block], input);
243       }
244       stackanalysis_printf("\t New in meet: %s\n", format(input).c_str());
245
246       // Step 2: see if the input has changed
247       if (input == blockInputs[block]) {
248          // No new work here
249          stackanalysis_printf("\t ... equal to current, skipping block\n");
250          continue;
251       }
252       stackanalysis_printf("\t ... inequal to current %s, analyzing block\n",
253          format(blockInputs[block]).c_str());
254
255       blockInputs[block] = input;
256
257       // Step 3: calculate our new outs
258       (*blockEffects)[block].apply(input, blockOutputs[block]);
259       stackanalysis_printf("\t ... output from block: %s\n",
260          format(blockOutputs[block]).c_str());
261
262       // Step 4: push all children on the worklist.
263       const Block::edgelist & outEdges = block->targets();
264       std::for_each(
265          boost::make_filter_iterator(epred2, outEdges.begin(), outEdges.end()),
266          boost::make_filter_iterator(epred2, outEdges.end(), outEdges.end()),
267          boost::bind(add_target, boost::ref(worklist), _1)
268       );
269
270       firstBlock = false;
271    }
272 }
273
274
275 bool StackAnalysis::getFunctionSummary(TransferSet &summary) {
276    df_init_debug();
277
278    if (!genInsnEffects()) return false;
279    assert(!blockEffects->empty());
280
281    const Function::const_blocklist &retBlocks = func->returnBlocks();
282    if (retBlocks.empty()) return false;  // No return edges means no summary
283
284    if (blockSummaryOutputs.empty()) {
285       summaryFixpoint();
286    }
287
288    // Join possible values at all return edges
289    TransferSet tempSummary;
290    for (auto iter = retBlocks.begin(); iter != retBlocks.end(); iter++) {
291       Block *currBlock = *iter;
292       meetSummary(blockSummaryOutputs[currBlock], tempSummary);
293    }
294
295    // Remove identity functions for simplicity
296    summary.clear();
297    for (auto iter = tempSummary.begin(); iter != tempSummary.end(); iter++) {
298       const Absloc &loc = iter->first;
299       const TransferFunc &tf = iter->second;
300       if (!tf.isIdentity()) {
301          summary[loc] = tf;
302       }
303    }
304
305    return true;
306 }
307
308
309 void StackAnalysis::summaryFixpoint() {
310    intra_nosink epred2;
311
312    std::queue<Block *> worklist;
313    worklist.push(func->entry());
314
315    bool firstBlock = true;
316    while (!worklist.empty()) {
317       Block *block = worklist.front();
318       worklist.pop();
319       stackanalysis_printf("\tSummary fixpoint analysis: visiting block at "
320          "0x%lx\n", block->start());
321
322       // Step 1: calculate the meet over the heights of all incoming
323       // intraprocedural blocks.
324       TransferSet input;
325       if (firstBlock) {
326          createSummaryEntryInput(input);
327          stackanalysis_printf("\t Primed initial block\n");
328       } else {
329          stackanalysis_printf("\t Calculating meet with block [%x-%x]\n",
330             block->start(), block->lastInsnAddr());
331          meetSummaryInputs(block, blockSummaryInputs[block], input);
332       }
333       stackanalysis_printf("\t New in meet: %s\n", format(input).c_str());
334
335       // Step 2: see if the input has changed
336       if (input == blockSummaryInputs[block] && !firstBlock) {
337          // No new work here
338          stackanalysis_printf("\t ... equal to current, skipping block\n");
339          continue;
340       }
341       stackanalysis_printf("\t ... inequal to current %s, analyzing block\n",
342          format(blockSummaryInputs[block]).c_str());
343
344       blockSummaryInputs[block] = input;
345
346       // Step 3: calculate our new outs
347       (*blockEffects)[block].accumulate(input, blockSummaryOutputs[block]);
348       stackanalysis_printf("\t ... output from block: %s\n",
349          format(blockSummaryOutputs[block]).c_str());
350
351       // Step 4: push all children on the worklist.
352       const Block::edgelist & outEdges = block->targets();
353       std::for_each(
354          boost::make_filter_iterator(epred2, outEdges.begin(), outEdges.end()),
355          boost::make_filter_iterator(epred2, outEdges.end(), outEdges.end()),
356          boost::bind(add_target, boost::ref(worklist), _1)
357       );
358
359       firstBlock = false;
360    }
361 }
362
363
364 void StackAnalysis::summarize() {
365    // Now that we know the actual inputs to each block, we create intervals by
366    // replaying the effects of each instruction.
367    if (intervals_ != NULL) delete intervals_;
368    intervals_ = new Intervals();
369
370    Function::blocklist bs = func->blocks();
371    for (auto bit = bs.begin(); bit != bs.end(); ++bit) {
372       Block *block = *bit;
373       AbslocState input = blockInputs[block];
374
375       std::map<Offset, TransferFuncs>::iterator iter;
376       for (iter = (*insnEffects)[block].begin();
377          iter != (*insnEffects)[block].end(); ++iter) {
378          Offset off = iter->first;
379          TransferFuncs &xferFuncs = iter->second;
380
381          // TODO: try to collapse these in some intelligent fashion
382          (*intervals_)[block][off] = input;
383
384          for (TransferFuncs::iterator iter2 = xferFuncs.begin();
385             iter2 != xferFuncs.end(); ++iter2) {
386             input[iter2->target] = iter2->apply(input);
387             if (input[iter2->target].isTop()) {
388                input.erase(iter2->target);
389             }
390          }
391       }
392       (*intervals_)[block][block->end()] = input;
393       assert(input == blockOutputs[block]);
394    }
395 }
396
397 void StackAnalysis::computeInsnEffects(ParseAPI::Block *block,
398    Instruction::Ptr insn, const Offset off, TransferFuncs &xferFuncs) {
399    stackanalysis_printf("\t\tInsn at 0x%lx\n", off);
400    entryID what = insn->getOperation().getID();
401
402    // Reminder: what we're interested in:
403    // a) Use of the stack pointer to define another register
404    //      Assumption: this is done by an e_mov and is a direct copy
405    //                  else bottom
406    // b) Use of another register to define the stack pointer
407    //      Assumption: see ^^
408    // c) Modification of the stack pointer
409    //
410    // The reason for these assumptions is to keep the analysis reasonable; also,
411    // other forms just don't occur.
412    //
413    // In summary, the stack pointer must be read or written for us to be
414    // interested.
415    //
416    // However, we need to detect when a register is destroyed. So if something
417    // is written, we assume it is destroyed.
418    //
419    // For now, we assume an all-to-all mapping for speed.
420
421    // Cases we handle
422    if (isCall(insn)) {
423       if (handleNormalCall(insn, block, off, xferFuncs)) return;
424       else if (handleThunkCall(insn, xferFuncs)) return;
425       else return handleDefault(insn, xferFuncs);
426    }
427
428    int sign = 1;
429    switch (what) {
430       case e_push:
431          sign = -1;
432          //FALLTHROUGH
433       case e_pop:
434          handlePushPop(insn, block, off, sign, xferFuncs);
435          break;
436       case e_ret_near:
437       case e_ret_far:
438          handleReturn(insn, xferFuncs);
439          break;
440       case e_lea:
441          handleLEA(insn, xferFuncs);
442          break;
443       case e_sub:
444          sign = -1;
445          //FALLTHROUGH
446       case e_add:
447       case e_addsd:
448          handleAddSub(insn, block, off, sign, xferFuncs);
449          break;
450       case e_leave:
451          handleLeave(block, off, xferFuncs);
452          break;
453       case e_pushfd:
454          sign = -1;
455          //FALLTHROUGH
456       case e_popfd:
457          handlePushPopFlags(sign, xferFuncs);
458          break;
459       case e_pushad:
460          sign = -1;
461          handlePushPopRegs(sign, xferFuncs);
462          break;
463       case e_popad:
464          // This nukes all registers
465          handleDefault(insn, xferFuncs);
466          break;
467       case power_op_addi:
468       case power_op_addic:
469          handlePowerAddSub(insn, sign, xferFuncs);
470          break;
471       case power_op_stwu:
472          handlePowerStoreUpdate(insn, xferFuncs);
473          break;
474       case e_mov:
475       case e_movsd_sse:
476          handleMov(insn, block, off, xferFuncs);
477          break;
478       case e_movzx:
479          handleZeroExtend(insn, block, off, xferFuncs);
480          break;
481       case e_movsx:
482       case e_movsxd:
483          handleSignExtend(insn, block, off, xferFuncs);
484          break;
485       case e_cbw:
486       case e_cwde:
487          handleSpecialSignExtend(insn, xferFuncs);
488          break;
489       case e_xor:
490          handleXor(insn, block, off, xferFuncs);
491          break;
492       case e_div:
493       case e_idiv:
494          handleDiv(insn, xferFuncs);
495          break;
496       case e_mul:
497       case e_imul:
498          handleMul(insn, xferFuncs);
499          break;
500       default:
501          handleDefault(insn, xferFuncs);
502    }
503 }
504
505 StackAnalysis::Height StackAnalysis::getStackCleanAmount(Function *func) {
506    // Cache previous work...
507    if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
508       return funcCleanAmounts[func];
509    }
510
511    if (!func->cleansOwnStack()) {
512       funcCleanAmounts[func] = 0;
513       return funcCleanAmounts[func];
514    }
515
516    InstructionDecoder decoder((const unsigned char*) NULL, 0,
517       func->isrc()->getArch());
518    unsigned char *cur;
519
520    std::set<Height> returnCleanVals;
521
522    Function::const_blocklist returnBlocks = func->returnBlocks();
523    for (auto rets = returnBlocks.begin(); rets != returnBlocks.end(); ++rets) {
524       Block *ret = *rets;
525       cur = (unsigned char *) ret->region()->getPtrToInstruction(
526          ret->lastInsnAddr());
527       Instruction::Ptr insn = decoder.decode(cur);
528
529       entryID what = insn->getOperation().getID();
530       if (what != e_ret_near) continue;
531
532       int val;
533       std::vector<Operand> ops;
534       insn->getOperands(ops);
535       if (ops.size() == 1) {
536          val = 0;
537       } else {
538          Result imm = ops[1].getValue()->eval();
539          assert(imm.defined);
540          val = (int) imm.val.s16val;
541       }
542       returnCleanVals.insert(Height(val));
543    }
544
545    Height clean = Height::meet(returnCleanVals);
546    if (clean == Height::top) {
547       // Non-returning or tail-call exits?
548       clean = Height::bottom;
549    }
550    funcCleanAmounts[func] = clean;
551
552    return clean;
553 }
554
555 StackAnalysis::StackAnalysis() : func(NULL), blockEffects(NULL),
556    insnEffects(NULL), intervals_(NULL), word_size(0) {}
557    
558 StackAnalysis::StackAnalysis(Function *f) : func(f), blockEffects(NULL),
559    insnEffects(NULL), intervals_(NULL) {
560    word_size = func->isrc()->getAddressWidth();
561    theStackPtr = Expression::Ptr(new RegisterAST(MachRegister::getStackPointer(
562       func->isrc()->getArch())));
563    thePC = Expression::Ptr(new RegisterAST(MachRegister::getPC(
564       func->isrc()->getArch())));
565 }
566
567 void StackAnalysis::debug() {
568 }
569
570 std::string StackAnalysis::TransferFunc::format() const {
571    std::stringstream ret;
572
573    ret << "[";
574    if (target.isValid())
575       ret << target.format();
576    else
577       ret << "<INVALID>";
578    ret << ":=";
579    if (isBottom()) ret << "<BOTTOM>";
580    else if (isRetop()) ret << "<re-TOP>";
581    else if (isTop()) ret << "<TOP>";
582    else {
583       bool foundType = false;
584       if (isCopy()) {
585          ret << from.format();
586          foundType = true;
587       }
588       if (isAbs()) {
589          ret << abs << dec;
590          foundType = true;
591       }
592       if (isSIB()) {
593          for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
594             if (iter != fromRegs.begin()) {
595                ret << "+";
596             }
597             ret << "(";
598             ret << (*iter).first.format() << "*" << (*iter).second.first;
599             if ((*iter).second.second) {
600                ret << ", will round to TOP or BOTTOM";
601             }
602             ret << ")";
603          }
604          foundType = true;
605       }
606       if (isDelta()) {
607          assert(foundType);
608          ret << "+" << delta;
609       }
610    }
611    if (isTopBottom()) {
612       ret << ", will round to TOP or BOTTOM";
613    }
614    ret << "]";
615    return ret.str();
616 }
617
618 std::string StackAnalysis::SummaryFunc::format() const {
619    stringstream ret;
620    for (TransferSet::const_iterator iter = accumFuncs.begin();
621         iter != accumFuncs.end(); ++iter) {
622       ret << iter->second.format() << endl;
623    }
624    return ret.str();
625 }
626
627
628 void StackAnalysis::findDefinedHeights(ParseAPI::Block* b, Address addr,
629    std::vector<std::pair<Absloc, Height> >& heights) {
630    if (func == NULL) return;
631
632    if (!intervals_) {
633       // Check annotation
634       func->getAnnotation(intervals_, Stack_Anno_Intervals);
635    }
636    if (!intervals_) {
637       // Analyze?
638       if (!analyze()) return;
639    }
640    assert(intervals_);
641    for (AbslocState::iterator i = (*intervals_)[b][addr].begin();
642       i != (*intervals_)[b][addr].end(); ++i) {
643       if (i->second.isTop()) continue;
644
645       stackanalysis_printf("\t\tAdding %s:%s to defined heights at 0x%lx\n",
646          i->first.format().c_str(), i->second.format().c_str(), addr);
647
648       heights.push_back(*i);
649    }
650 }
651
652 StackAnalysis::Height StackAnalysis::find(Block *b, Address addr, Absloc loc) {
653    Height ret; // Defaults to "top"
654
655    if (func == NULL) return ret;
656
657    if (!intervals_) {
658       // Check annotation
659       func->getAnnotation(intervals_, Stack_Anno_Intervals);
660    }
661    if (!intervals_) {
662       // Analyze?
663       if (!analyze()) return Height();
664    }
665    assert(intervals_);
666
667    //(*intervals_)[b].find(addr, state);
668    //  ret = (*intervals_)[b][addr][reg];
669    Intervals::iterator iter = intervals_->find(b);
670    if (iter == intervals_->end()) {
671       // How do we return "you stupid idiot"?
672       return Height::bottom;
673    }
674
675    StateIntervals &sintervals = iter->second;
676    if (sintervals.empty()) {
677       return Height::bottom;
678    }
679    // Find the last instruction that is <= addr
680    StateIntervals::iterator i = sintervals.lower_bound(addr);
681    if ((i == sintervals.end() && !sintervals.empty()) ||
682       (i->first != addr && i != sintervals.begin())) {
683       i--;
684    }
685    if (i == sintervals.end()) return Height::bottom;
686
687    ret = i->second[loc];
688
689    if (ret.isTop()) {
690       return Height::bottom;
691    }
692    return ret;
693 }
694
695 StackAnalysis::Height StackAnalysis::findSP(Block *b, Address addr) {
696    return find(b, addr, Absloc(sp()));
697 }
698
699 StackAnalysis::Height StackAnalysis::findFP(Block *b, Address addr) {
700    return find(b, addr, Absloc(fp()));
701 }
702
703 std::ostream &operator<<(std::ostream &os,
704    const Dyninst::StackAnalysis::Height &h) {
705    os << "STACK_SLOT[" << h.format() << "]";
706    return os;
707 }
708
709 ///////////////////
710 // Insn effect fragments
711 ///////////////////
712
713 // Visitor class to evaluate stack heights and PC-relative addresses
714 class StateEvalVisitor : public Visitor {
715 public:
716    // addr is the starting address of instruction insn.
717    // insn is the instruction containing the expression to evaluate.
718    StateEvalVisitor(Address addr, Instruction::Ptr insn,
719       StackAnalysis::AbslocState *s) : defined(true), state(s) {
720       rip = addr + insn->size();
721    }
722
723    StateEvalVisitor() : defined(false), state(NULL), rip(0) {}
724
725    bool isDefined() {
726       return defined && results.size() == 1;
727    }
728
729    std::pair<Address, bool> getResult() {
730       return isDefined() ? results.back() : make_pair((Address) 0, false);
731    }
732
733    virtual void visit(BinaryFunction *bf) {
734       if (!defined) return;
735
736       Address arg1 = results.back().first;
737       bool isHeight1 = results.back().second;
738       results.pop_back();
739       Address arg2 = results.back().first;
740       bool isHeight2 = results.back().second;
741       results.pop_back();
742
743       if (bf->isAdd()) {
744          if (isHeight1 && isHeight2) {
745             defined = false;
746          } else {
747             results.push_back(make_pair(arg1 + arg2, isHeight1 || isHeight2));
748          }
749       } else if (bf->isMultiply()) {
750          if (isHeight1 || isHeight2) {
751             defined = false;
752          } else {
753             results.push_back(make_pair(arg1 * arg2, false));
754          }
755       } else {
756          defined = false;
757       }
758    }
759
760    virtual void visit(Immediate *imm) {
761       if (!defined) return;
762
763       results.push_back(make_pair(imm->eval().convert<Address>(), false));
764    }
765
766    virtual void visit(RegisterAST *rast) {
767       if (!defined) return;
768
769       MachRegister reg = rast->getID();
770       if (reg == x86::eip || reg == x86_64::eip || reg == x86_64::rip) {
771          results.push_back(make_pair(rip, false));
772       } else if (state != NULL) {
773          auto regState = state->find(Absloc(reg));
774          if (regState == state->end() || regState->second.isTop() ||
775             regState->second.isBottom()) {
776             defined = false;
777          } else {
778             results.push_back(make_pair(regState->second.height(), true));
779          }
780       } else {
781          defined = false;
782       }
783    }
784
785    virtual void visit(Dereference *) {
786       defined = false;
787    }
788
789 private:
790    bool defined;
791    StackAnalysis::AbslocState *state;
792    Address rip;
793
794    // Stack for calculations
795    // bool is true if the value in Address is a stack height
796    std::deque<std::pair<Address, bool>> results;
797
798 };
799
800 void StackAnalysis::handleXor(Instruction::Ptr insn, Block *block,
801    const Offset off, TransferFuncs &xferFuncs) {
802    std::vector<Operand> operands;
803    insn->getOperands(operands);
804    assert(operands.size() == 2);
805
806    // Handle the case where a register is being zeroed out.
807    // We recognize such cases as follows:
808    //   1. Exactly one register is both read and written
809    //   2. The Expression tree for each operand consists of a single leaf node
810    std::set<RegisterAST::Ptr> readSet;
811    std::set<RegisterAST::Ptr> writtenSet;
812    operands[0].getWriteSet(writtenSet);
813    operands[1].getReadSet(readSet);
814
815    std::vector<Expression::Ptr> children0;
816    std::vector<Expression::Ptr> children1;
817    operands[0].getValue()->getChildren(children0);
818    operands[1].getValue()->getChildren(children1);
819
820    if (readSet.size() == 1 && writtenSet.size() == 1 &&
821       (*readSet.begin())->getID() == (*writtenSet.begin())->getID() &&
822       children0.size() == 0 && children1.size() == 0) {
823       // xor reg1, reg1
824       const MachRegister &reg = (*writtenSet.begin())->getID();
825       Absloc loc(reg);
826       xferFuncs.push_back(TransferFunc::absFunc(loc, 0));
827       retopBaseSubReg(reg, xferFuncs);
828       return;
829    }
830
831
832    if (insn->writesMemory()) {
833       // xor mem1, reg2/imm2
834       assert(writtenSet.size() == 0);
835
836       // Extract the expression inside the dereference
837       std::vector<Expression::Ptr> &addrExpr = children0;
838       assert(addrExpr.size() == 1);
839
840       // Try to determine the written memory address
841       Absloc writtenLoc;
842       StateEvalVisitor visitor;
843       if (intervals_ == NULL) {
844          visitor = StateEvalVisitor(off, insn, NULL);
845       } else {
846          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
847       }
848       addrExpr[0]->apply(&visitor);
849       if (visitor.isDefined()) {
850          std::pair<Address, bool> resultPair = visitor.getResult();
851          if (resultPair.second) {
852             // We have a stack slot
853             writtenLoc = Absloc(resultPair.first, 0, NULL);
854          } else {
855             // We have a static address
856             writtenLoc = Absloc(resultPair.first);
857          }
858       } else {
859          // Couldn't determine written location, so assume it's not on the stack
860          // and ignore it.
861          return;
862       }
863
864       if (readSet.size() > 0) {
865          // xor mem1, reg2
866          assert(readSet.size() == 1);
867          Absloc from((*readSet.begin())->getID());
868          std::map<Absloc, std::pair<long, bool>> fromRegs;
869          fromRegs[writtenLoc] = std::make_pair(1, true);
870          fromRegs[from] = std::make_pair(1, true);
871          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, 0, writtenLoc));
872       } else {
873          // xor mem1, imm2
874          // Xor with immediate.  Set topBottom on target loc
875          Expression::Ptr immExpr = operands[1].getValue();
876          assert(typeid(*immExpr) == typeid(Immediate));
877          xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc,
878             true));
879       }
880       return;
881    }
882
883
884    assert(writtenSet.size() == 1);
885    MachRegister written = (*writtenSet.begin())->getID();
886    Absloc writtenLoc(written);
887
888    if (insn->readsMemory()) {
889       // xor reg1, mem2
890       // Extract the expression inside the dereference
891       std::vector<Expression::Ptr> &addrExpr = children1;
892       assert(addrExpr.size() == 1);
893
894       // Try to determine the read memory address
895       StateEvalVisitor visitor;
896       if (intervals_ == NULL) {
897          visitor = StateEvalVisitor(off, insn, NULL);
898       } else {
899          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
900       }
901       addrExpr[0]->apply(&visitor);
902       if (visitor.isDefined()) {
903          std::pair<Address, bool> resultPair = visitor.getResult();
904          Absloc readLoc;
905          if (resultPair.second) {
906             // We have a stack slot
907             readLoc = Absloc(resultPair.first, 0, NULL);
908          } else {
909             // We have a static address
910             readLoc = Absloc(resultPair.first);
911          }
912          std::map<Absloc, std::pair<long, bool>> fromRegs;
913          fromRegs[writtenLoc] = std::make_pair(1, true);
914          fromRegs[readLoc] = std::make_pair(1, true);
915          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, 0, writtenLoc));
916          copyBaseSubReg(written, xferFuncs);
917       } else {
918          // Couldn't determine the read location.  Assume it's not on the stack.
919          xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc,
920             true));
921          copyBaseSubReg(written, xferFuncs);
922       }
923       return;
924    }
925
926
927    // xor reg1, reg2/imm2
928    MachRegister read;
929    if (!readSet.empty()) {
930       assert(readSet.size() == 1);
931       read = (*readSet.begin())->getID();
932    }
933    Absloc readLoc(read);
934
935    if (read.isValid()) {
936       // xor reg1, reg2
937       std::map<Absloc, std::pair<long, bool>> fromRegs;
938       fromRegs[writtenLoc] = std::make_pair(1, true);
939       fromRegs[readLoc] = std::make_pair(1, true);
940       xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, 0, writtenLoc));
941       copyBaseSubReg(written, xferFuncs);
942    } else {
943       // xor reg1, imm1
944       InstructionAPI::Expression::Ptr readExpr = operands[1].getValue();
945       assert(typeid(*readExpr) == typeid(InstructionAPI::Immediate));
946       xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc, true));
947       copyBaseSubReg(written, xferFuncs);
948    }
949 }
950
951
952 void StackAnalysis::handleDiv(Instruction::Ptr insn,
953    TransferFuncs &xferFuncs) {
954    stackanalysis_printf("\t\t\thandleDiv: %s\n", insn->format().c_str());
955    std::vector<Operand> operands;
956    insn->getOperands(operands);
957    assert(operands.size() == 3);
958
959    Expression::Ptr quotient = operands[1].getValue();
960    Expression::Ptr remainder = operands[0].getValue();
961    Expression::Ptr divisor = operands[2].getValue();
962    assert(typeid(*quotient) == typeid(RegisterAST));
963    assert(typeid(*remainder) == typeid(RegisterAST));
964    assert(typeid(*divisor) != typeid(Immediate));
965
966    MachRegister quotientReg = (boost::dynamic_pointer_cast<InstructionAPI::
967       RegisterAST>(quotient))->getID();
968    MachRegister remainderReg = (boost::dynamic_pointer_cast<InstructionAPI::
969       RegisterAST>(remainder))->getID();
970
971    xferFuncs.push_back(TransferFunc::retopFunc(Absloc(quotientReg)));
972    xferFuncs.push_back(TransferFunc::retopFunc(Absloc(remainderReg)));
973    retopBaseSubReg(quotientReg, xferFuncs);
974    retopBaseSubReg(remainderReg, xferFuncs);
975 }
976
977
978 void StackAnalysis::handleMul(Instruction::Ptr insn,
979    TransferFuncs &xferFuncs) {
980    // MULs have a few forms:
981    //   1. mul reg1, reg2/mem2
982    //     -- reg1 = reg1 * reg2/mem2
983    //   2. mul reg1, reg2/mem2, imm3
984    //     -- reg1 = reg2/mem2 * imm3
985    //   3. mul reg1, reg2, reg3/mem3
986    //     -- reg1:reg2 = reg2 * reg3/mem3
987    std::vector<Operand> operands;
988    insn->getOperands(operands);
989    assert(operands.size() == 2 || operands.size() == 3);
990
991    Expression::Ptr target = operands[0].getValue();
992    assert(typeid(*target) == typeid(RegisterAST));
993    MachRegister targetReg = (boost::dynamic_pointer_cast<InstructionAPI::
994       RegisterAST>(target))->getID();
995
996    if (operands.size() == 2) {
997       // Form 1
998       xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
999       retopBaseSubReg(targetReg, xferFuncs);
1000    } else {
1001       Expression::Ptr multiplicand = operands[1].getValue();
1002       Expression::Ptr multiplier = operands[2].getValue();
1003
1004       if (typeid(*multiplier) == typeid(Immediate)) {
1005          // Form 2
1006          assert(typeid(*multiplicand) == typeid(RegisterAST) ||
1007             typeid(*multiplicand) == typeid(Dereference));
1008          long multiplierVal = multiplier->eval().convert<long>();
1009          if (multiplierVal == 0) {
1010             xferFuncs.push_back(TransferFunc::absFunc(Absloc(targetReg), 0));
1011             retopBaseSubReg(targetReg, xferFuncs);
1012          } else if (multiplierVal == 1) {
1013             if (typeid(*multiplicand) == typeid(RegisterAST)) {
1014                // mul reg1, reg2, 1
1015                MachRegister multiplicandReg = boost::dynamic_pointer_cast<
1016                   RegisterAST>(multiplicand)->getID();
1017                Absloc targetLoc(targetReg);
1018                Absloc multiplicandLoc(multiplicandReg);
1019                xferFuncs.push_back(TransferFunc::copyFunc(multiplicandLoc,
1020                   targetLoc));
1021                copyBaseSubReg(targetReg, xferFuncs);
1022             } else {
1023                // mul reg1, mem2, 1
1024                Absloc targetLoc(targetReg);
1025                xferFuncs.push_back(TransferFunc::bottomFunc(targetLoc));
1026                bottomBaseSubReg(targetReg, xferFuncs);
1027             }
1028          } else {
1029             xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
1030             retopBaseSubReg(targetReg, xferFuncs);
1031          }
1032       } else {
1033          // Form 3
1034          assert(typeid(*multiplicand) == typeid(RegisterAST));
1035          assert(typeid(*multiplier) == typeid(RegisterAST) ||
1036             typeid(*multiplier) == typeid(Dereference));
1037          MachRegister multiplicandReg = boost::dynamic_pointer_cast<
1038             RegisterAST>(multiplicand)->getID();
1039          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
1040          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(multiplicandReg)));
1041          retopBaseSubReg(targetReg, xferFuncs);
1042          retopBaseSubReg(multiplicandReg, xferFuncs);
1043       }
1044    }
1045 }
1046
1047
1048 void StackAnalysis::handlePushPop(Instruction::Ptr insn, Block *block,
1049    const Offset off, int sign, TransferFuncs &xferFuncs) {
1050
1051    long delta = 0;
1052    Operand arg = insn->getOperand(0);
1053    // Why was this here? bernat, 12JAN11
1054    if (arg.getValue()->eval().defined) {
1055       delta = sign * word_size;
1056       stackanalysis_printf(
1057          "\t\t\t Stack height changed by evaluated push/pop: %lx\n", delta);
1058    } else {
1059       delta = sign * arg.getValue()->size();
1060       //cerr << "Odd case: set delta to " << hex << delta << dec <<
1061       //   " for instruction " << insn->format() << endl;
1062       stackanalysis_printf(
1063          "\t\t\t Stack height changed by unevalled push/pop: %lx\n", delta);
1064    }
1065    //   delta = sign *arg.getValue()->size();
1066    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
1067    copyBaseSubReg(sp(), xferFuncs);
1068
1069    if (insn->getOperation().getID() == e_push && insn->writesMemory()) {
1070       // This is a push.  Let's record the value pushed on the stack if
1071       // possible.
1072       if (intervals_ != NULL) {
1073          Absloc sploc(sp());
1074          Height spHeight = (*intervals_)[block][off][sploc];
1075          if (!spHeight.isTop() && !spHeight.isBottom()) {
1076             // Get written stack slot
1077             long writtenSlotHeight = spHeight.height() - word_size;
1078             Absloc writtenLoc(writtenSlotHeight, 0, NULL);
1079
1080             // Get copied register
1081             Expression::Ptr readExpr = insn->getOperand(0).getValue();
1082             assert(typeid(*readExpr) == typeid(RegisterAST));
1083             MachRegister readReg = boost::dynamic_pointer_cast<RegisterAST>(
1084                readExpr)->getID();
1085             Absloc readLoc(readReg);
1086
1087             xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1088          }
1089       }
1090    } else if (insn->getOperation().getID() == e_pop && !insn->writesMemory()) {
1091       // This is a pop.  Let's record the value popped if possible.
1092
1093       // Get target register
1094       Expression::Ptr targExpr = insn->getOperand(0).getValue();
1095       assert(typeid(*targExpr) == typeid(RegisterAST));
1096       MachRegister targReg = boost::dynamic_pointer_cast<RegisterAST>(
1097          targExpr)->getID();
1098       Absloc targLoc(targReg);
1099
1100       if (intervals_ != NULL) {
1101          Absloc sploc(sp());
1102          Height spHeight = (*intervals_)[block][off][sploc];
1103          if (spHeight.isTop()) {
1104             // Load from a topped location. Since StackMod fails when storing
1105             // to an undetermined topped location, it is safe to assume the
1106             // value loaded here is not a stack height.
1107             xferFuncs.push_back(TransferFunc::retopFunc(targLoc));
1108             retopBaseSubReg(targReg, xferFuncs);
1109          } else if (spHeight.isBottom()) {
1110             xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1111             bottomBaseSubReg(targReg, xferFuncs);
1112          } else {
1113             // Get copied stack slot
1114             long readSlotHeight = spHeight.height();
1115             Absloc readLoc(readSlotHeight, 0, NULL);
1116
1117             xferFuncs.push_back(TransferFunc::copyFunc(readLoc, targLoc));
1118             copyBaseSubReg(targReg, xferFuncs);
1119          }
1120       } else {
1121          xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1122          bottomBaseSubReg(targReg, xferFuncs);
1123       }
1124    } else {
1125       assert(false);
1126    }
1127 }
1128
1129 void StackAnalysis::handleReturn(Instruction::Ptr insn,
1130    TransferFuncs &xferFuncs) {
1131    long delta = 0;
1132    std::vector<Operand> operands;
1133    insn->getOperands(operands);
1134    if (operands.size() < 2) {
1135       delta = word_size;
1136    } else {
1137       fprintf(stderr, "Unhandled RET instruction: %s\n",
1138          insn->format().c_str());
1139       assert(false);
1140    }
1141 /*   else if (operands.size() == 1) {
1142       // Ret immediate
1143       Result imm = operands[0].getValue()->eval();
1144       if (imm.defined) {
1145          delta = word_size + imm.convert<int>();
1146       }
1147       else {
1148          stackanalysis_printf("\t\t\t Stack height changed by return: bottom\n");
1149          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(sp())));
1150       }
1151    }
1152 */
1153    stackanalysis_printf("\t\t\t Stack height changed by return: %lx\n", delta);
1154    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
1155    copyBaseSubReg(sp(), xferFuncs);
1156 }
1157
1158
1159 void StackAnalysis::handleAddSub(Instruction::Ptr insn, Block *block,
1160    const Offset off, int sign, TransferFuncs &xferFuncs) {
1161    // Possible forms for add/sub:
1162    //   1. add reg1, reg2
1163    //     -- reg1 = reg1 + reg2
1164    //   2. add reg1, mem2
1165    //     -- reg1 = reg1 + mem2
1166    //   3. add mem1, reg2
1167    //     -- mem1 = mem1 + reg2
1168    //   4. add reg1, imm2
1169    //     -- reg1 = reg1 + imm2
1170    //   5. add mem1, imm2
1171    //     -- mem1 = mem1 + imm2
1172    //
1173    //   #1 is handled by setting reg1 to a sibFunc of reg1 and reg2.
1174    //   #2 depends on whether or not the location of mem2 can be determined
1175    //      statically.
1176    //      a. If it can, reg1 is set to a sibFunc of reg1 and mem2.
1177    //      b. Otherwise, reg1 is set to topBottom.
1178    //   #3 depends on whether or not the location of mem1 can be determined
1179    //      statically.
1180    //      a. If it can, mem1 is set to a sibFunc of mem1 and reg2.
1181    //      b. Otherwise, nothing happens.
1182    //   #4 is handled with a delta.
1183    //   #5 depends on whether or not the location of mem1 can be determined
1184    //      statically.
1185    //      a. If it can, mem1 is handled with a delta.
1186    //      b. Otherwise, nothing happens.
1187
1188    stackanalysis_printf("\t\t\t handleAddSub, insn = %s\n",
1189       insn->format().c_str());
1190    Architecture arch = insn->getArch();  // Needed for debug messages
1191    std::vector<Operand> operands;
1192    insn->getOperands(operands);
1193    assert(operands.size() == 2);
1194
1195    std::set<RegisterAST::Ptr> readSet;
1196    std::set<RegisterAST::Ptr> writeSet;
1197    operands[1].getReadSet(readSet);
1198    operands[0].getWriteSet(writeSet);
1199
1200    if (insn->writesMemory()) {
1201       // Cases 3 and 5
1202       assert(writeSet.size() == 0);
1203       stackanalysis_printf("\t\t\tMemory add/sub to: %s\n",
1204          operands[0].format(arch).c_str());
1205
1206       // Extract the expression inside the dereference
1207       std::vector<Expression::Ptr> addrExpr;
1208       operands[0].getValue()->getChildren(addrExpr);
1209       assert(addrExpr.size() == 1);
1210
1211       // Try to determine the written memory address
1212       Absloc writtenLoc;
1213       StateEvalVisitor visitor;
1214       if (intervals_ == NULL) {
1215          visitor = StateEvalVisitor(off, insn, NULL);
1216       } else {
1217          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1218       }
1219       addrExpr[0]->apply(&visitor);
1220       if (visitor.isDefined()) {
1221          std::pair<Address, bool> resultPair = visitor.getResult();
1222          if (resultPair.second) {
1223             // We have a stack slot
1224             writtenLoc = Absloc(resultPair.first, 0, NULL);
1225          } else {
1226             // We have a static address
1227             writtenLoc = Absloc(resultPair.first);
1228          }
1229          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1230             writtenLoc.format().c_str());
1231       } else {
1232          // Cases 3b and 5b
1233          stackanalysis_printf("\t\t\tCan't determine location\n");
1234          return;
1235       }
1236
1237       if (readSet.size() > 0) {
1238          // Case 3a
1239          assert(readSet.size() == 1);
1240          std::map<Absloc, std::pair<long, bool>> terms;
1241          Absloc src((*readSet.begin())->getID());
1242          Absloc &dest = writtenLoc;
1243          terms[src] = make_pair(sign, false);
1244          terms[dest] = make_pair(1, false);
1245          xferFuncs.push_back(TransferFunc::sibFunc(terms, 0, dest));
1246       } else {
1247          // Case 5a
1248          Expression::Ptr immExpr = operands[1].getValue();
1249          assert(typeid(*immExpr) == typeid(Immediate));
1250          long immVal = immExpr->eval().convert<long>();
1251          xferFuncs.push_back(TransferFunc::deltaFunc(writtenLoc,
1252             sign * immVal));
1253       }
1254       return;
1255    }
1256
1257    // Cases 1, 2, and 4
1258    assert(writeSet.size() == 1);
1259    MachRegister written = (*writeSet.begin())->getID();
1260    Absloc writtenLoc(written);
1261
1262    if (insn->readsMemory()) {
1263       // Case 2
1264       stackanalysis_printf("\t\t\tAdd/sub from: %s\n",
1265          operands[1].format(arch).c_str());
1266
1267       // Extract the expression inside the dereference
1268       std::vector<Expression::Ptr> addrExpr;
1269       operands[1].getValue()->getChildren(addrExpr);
1270       assert(addrExpr.size() == 1);
1271
1272       // Try to determine the read memory address
1273       StateEvalVisitor visitor;
1274       if (intervals_ == NULL) {
1275          visitor = StateEvalVisitor(off, insn, NULL);
1276       } else {
1277          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1278       }
1279       addrExpr[0]->apply(&visitor);
1280       if (visitor.isDefined()) {
1281          // Case 2a
1282          std::pair<Address, bool> resultPair = visitor.getResult();
1283          Absloc readLoc;
1284          if (resultPair.second) {
1285             // We have a stack slot
1286             readLoc = Absloc(resultPair.first, 0, NULL);
1287          } else {
1288             // We have a static address
1289             readLoc = Absloc(resultPair.first);
1290          }
1291          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1292             readLoc.format().c_str());
1293          std::map<Absloc, std::pair<long, bool>> terms;
1294          terms[readLoc] = make_pair(sign, false);
1295          terms[writtenLoc] = make_pair(1, false);
1296          xferFuncs.push_back(TransferFunc::sibFunc(terms, 0, writtenLoc));
1297          copyBaseSubReg(written, xferFuncs);
1298       } else {
1299          // Case 2b
1300          stackanalysis_printf("\t\t\tCan't determine location\n");
1301          xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc,
1302             true));
1303          copyBaseSubReg(written, xferFuncs);
1304       }
1305       return;
1306    }
1307
1308    Result res = operands[1].getValue()->eval();
1309    if (res.defined) {
1310       // Case 4
1311       long delta = sign * extractDelta(res);
1312       stackanalysis_printf("\t\t\t Register changed by add/sub: %lx\n", delta);
1313       xferFuncs.push_back(TransferFunc::deltaFunc(writtenLoc, delta));
1314       copyBaseSubReg(written, xferFuncs);
1315    } else {
1316       // Case 1
1317       std::map<Absloc, std::pair<long, bool>> terms;
1318       Absloc src((*readSet.begin())->getID());
1319       Absloc &dest = writtenLoc;
1320       terms[src] = make_pair(sign, false);
1321       terms[dest] = make_pair(1, false);
1322       xferFuncs.push_back(TransferFunc::sibFunc(terms, 0, dest));
1323       copyBaseSubReg(written, xferFuncs);
1324    }
1325 }
1326
1327 void StackAnalysis::handleLEA(Instruction::Ptr insn,
1328    TransferFuncs &xferFuncs) {
1329    // LEA has a few patterns:
1330    //   op0: target register
1331    //-------------------------------
1332    //   op1: reg + reg * imm + imm
1333    //            or
1334    //   op1: reg + reg * imm
1335    //            or
1336    //   op1: imm + reg * imm
1337    //            or
1338    //   op1: reg + imm
1339    //            or
1340    //   op1: reg
1341    //
1342
1343    stackanalysis_printf("\t\t\t handleLEA, insn = %s\n",
1344       insn->format().c_str());
1345
1346    std::set<RegisterAST::Ptr> readSet;
1347    std::set<RegisterAST::Ptr> writtenSet;
1348    insn->getOperand(0).getWriteSet(writtenSet);
1349    insn->getOperand(1).getReadSet(readSet);
1350    assert(writtenSet.size() == 1);
1351    assert(readSet.size() == 1 || readSet.size() == 2);
1352    MachRegister written = (*writtenSet.begin())->getID();
1353    Absloc writeloc(written);
1354
1355    InstructionAPI::Operand srcOperand = insn->getOperand(1);
1356    InstructionAPI::Expression::Ptr srcExpr = srcOperand.getValue();
1357    std::vector<InstructionAPI::Expression::Ptr> children;
1358    srcExpr->getChildren(children);
1359
1360    stackanalysis_printf("\t\t\t\t srcOperand = %s\n",
1361       srcExpr->format().c_str());
1362
1363    if (readSet.size() == 1) {
1364       InstructionAPI::Expression::Ptr regExpr, scaleExpr, deltaExpr;
1365       bool foundScale = false;
1366       bool foundDelta = false;
1367
1368       if (children.size() == 2) {
1369          if (typeid(*children[0]) == typeid(Immediate)) {
1370             // op1: imm + reg * imm
1371             deltaExpr = children[0];
1372             Expression::Ptr scaleIndexExpr = children[1];
1373             assert(typeid(*scaleIndexExpr) == typeid(BinaryFunction));
1374             children.clear();
1375             scaleIndexExpr->getChildren(children);
1376
1377             regExpr = children[0];
1378             scaleExpr = children[1];
1379             assert(typeid(*regExpr) == typeid(RegisterAST));
1380             assert(typeid(*scaleExpr) == typeid(Immediate));
1381             foundScale = true;
1382             foundDelta = true;
1383          } else if (typeid(*children[0]) == typeid(RegisterAST)) {
1384             // op1: reg + imm
1385             regExpr = children[0];
1386             deltaExpr = children[1];
1387             stackanalysis_printf("\t\t\t\t reg: %s\n",
1388                regExpr->format().c_str());
1389             stackanalysis_printf("\t\t\t\t delta: %s\n",
1390                deltaExpr->format().c_str());
1391             assert(typeid(*regExpr) == typeid(RegisterAST));
1392             assert(typeid(*deltaExpr) == typeid(Immediate));
1393             foundDelta = true;
1394          } else {
1395             assert(false);
1396          }
1397       } else if (children.size() == 0) {
1398          // op1: reg
1399          regExpr = srcExpr;
1400          assert(typeid(*regExpr) == typeid(RegisterAST));
1401       } else {
1402          assert(false);
1403       }
1404
1405       MachRegister reg = (boost::dynamic_pointer_cast<InstructionAPI::
1406          RegisterAST>(regExpr))->getID();
1407
1408       long scale = 1;
1409       if (foundScale) {
1410          scale = scaleExpr->eval().convert<long>();
1411       }
1412
1413       long delta = 0;
1414       if (foundDelta) {
1415          delta = extractDelta(deltaExpr->eval());
1416       }
1417
1418       if (foundScale) {
1419          std::map<Absloc,std::pair<long, bool> > fromRegs;
1420          fromRegs.insert(make_pair(Absloc(reg), make_pair(scale, false)));
1421          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, delta, writeloc));
1422          copyBaseSubReg(written, xferFuncs);
1423       } else {
1424          Absloc readloc(reg);
1425          TransferFunc lea = TransferFunc::copyFunc(readloc, writeloc);
1426          lea.delta = delta;
1427          xferFuncs.push_back(lea);
1428          copyBaseSubReg(written, xferFuncs);
1429       }
1430    } else if (readSet.size() == 2) {
1431       Expression::Ptr baseExpr, indexExpr, scaleExpr, deltaExpr;
1432       bool foundDelta = false;
1433
1434       assert(children.size() == 2);
1435       if (typeid(*children[1]) == typeid(Immediate)) {
1436          // op1: reg + reg * imm + imm
1437          // Extract the delta and continue on to get base, index, and scale
1438          deltaExpr = children[1];
1439          stackanalysis_printf("\t\t\t\t delta: %s\n",
1440             deltaExpr->format().c_str());
1441          Expression::Ptr sibExpr = children[0];
1442          assert(typeid(*sibExpr) == typeid(BinaryFunction));
1443          children.clear();
1444          sibExpr->getChildren(children);
1445          assert(children.size() == 2);
1446          foundDelta = true;
1447       }
1448
1449       // op1: reg + reg * imm
1450       baseExpr = children[0];
1451       Expression::Ptr scaleIndexExpr = children[1];
1452       stackanalysis_printf("\t\t\t\t base: %s\n", baseExpr->format().c_str());
1453       assert(typeid(*scaleIndexExpr) == typeid(BinaryFunction));
1454
1455       // Extract the index and scale
1456       children.clear();
1457       scaleIndexExpr->getChildren(children);
1458       assert(children.size() == 2);
1459       indexExpr = children[0];
1460       scaleExpr = children[1];
1461       stackanalysis_printf("\t\t\t\t index: %s\n",
1462          indexExpr->format().c_str());
1463       stackanalysis_printf("\t\t\t\t scale: %s\n",
1464          scaleExpr->format().c_str());
1465
1466       assert(typeid(*baseExpr) == typeid(RegisterAST));
1467       assert(typeid(*indexExpr) == typeid(RegisterAST));
1468       assert(typeid(*scaleExpr) == typeid(Immediate));
1469
1470       MachRegister base = (boost::dynamic_pointer_cast<InstructionAPI::
1471          RegisterAST>(baseExpr))->getID();
1472       MachRegister index = (boost::dynamic_pointer_cast<InstructionAPI::
1473          RegisterAST>(indexExpr))->getID();
1474       long scale = scaleExpr->eval().convert<long>();
1475
1476       long delta = 0;
1477       if (foundDelta) {
1478          Result deltaRes = deltaExpr->eval();
1479          delta = extractDelta(deltaRes);
1480       }
1481
1482       assert(base.isValid() && index.isValid() && scale != -1);
1483
1484       // Consolidate when possible
1485       if (base == index) {
1486          base = MachRegister();
1487          scale++;
1488       }
1489
1490       std::map<Absloc,std::pair<long,bool> > fromRegs;
1491       if (base.isValid()) {
1492          fromRegs.insert(make_pair(Absloc(base), make_pair(1, false)));
1493       }
1494       fromRegs.insert(make_pair(Absloc(index), make_pair(scale, false)));
1495       xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, delta, writeloc));
1496       copyBaseSubReg(written, xferFuncs);
1497    } else {
1498       assert(false);
1499    }
1500 }
1501
1502 void StackAnalysis::handleLeave(Block *block, const Offset off,
1503    TransferFuncs &xferFuncs) {
1504    // This is... mov esp, ebp; pop ebp.
1505    // Handle it as such.
1506
1507    // mov esp, ebp;
1508    xferFuncs.push_back(TransferFunc::copyFunc(Absloc(fp()), Absloc(sp())));
1509    copyBaseSubReg(fp(), xferFuncs);
1510
1511    // pop ebp: adjust stack pointer
1512    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), word_size));
1513    copyBaseSubReg(sp(), xferFuncs);
1514
1515    // pop ebp: copy value from stack to ebp
1516    Absloc targLoc(fp());
1517    if (intervals_ != NULL) {
1518       Absloc sploc(sp());
1519       Height spHeight = (*intervals_)[block][off][sploc];
1520       if (spHeight.isTop()) {
1521          // Load from a topped location. Since StackMod fails when storing
1522          // to an undetermined topped location, it is safe to assume the
1523          // value loaded here is not a stack height.
1524          xferFuncs.push_back(TransferFunc::retopFunc(targLoc));
1525          retopBaseSubReg(fp(), xferFuncs);
1526       } else if (spHeight.isBottom()) {
1527          xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1528          bottomBaseSubReg(fp(), xferFuncs);
1529       } else {
1530          // Get copied stack slot
1531          long readSlotHeight = spHeight.height();
1532          Absloc readLoc(readSlotHeight, 0, NULL);
1533
1534          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, targLoc));
1535          copyBaseSubReg(fp(), xferFuncs);
1536       }
1537    } else {
1538       xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1539       bottomBaseSubReg(fp(), xferFuncs);
1540    }
1541 }
1542
1543 void StackAnalysis::handlePushPopFlags(int sign, TransferFuncs &xferFuncs) {
1544    // Fixed-size push/pop
1545    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), sign * word_size));
1546    copyBaseSubReg(sp(), xferFuncs);
1547 }
1548
1549 void StackAnalysis::handlePushPopRegs(int sign, TransferFuncs &xferFuncs) {
1550    // Fixed-size push/pop
1551    // 8 registers
1552    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()),
1553       sign * 8 * word_size));
1554    copyBaseSubReg(sp(), xferFuncs);
1555 }
1556
1557 void StackAnalysis::handlePowerAddSub(Instruction::Ptr insn, int sign,
1558    TransferFuncs &xferFuncs) {
1559
1560    // Add/subtract are op0 = op1 +/- op2; we'd better read the stack pointer as
1561    // well as writing it
1562    if (!insn->isRead(theStackPtr) || !insn->isWritten(theStackPtr)) {
1563       return handleDefault(insn, xferFuncs);
1564    }
1565    
1566    Operand arg = insn->getOperand(2);
1567    Result res = arg.getValue()->eval();
1568    Absloc sploc(sp());
1569    if (res.defined) {
1570       xferFuncs.push_back(TransferFunc::deltaFunc(sploc,
1571          sign * res.convert<long>()));
1572       copyBaseSubReg(sp(), xferFuncs);
1573       stackanalysis_printf(
1574          "\t\t\t Stack height changed by evalled add/sub: %lx\n",
1575          sign * res.convert<long>());
1576    } else {
1577       xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1578       bottomBaseSubReg(sp(), xferFuncs);
1579       stackanalysis_printf(
1580          "\t\t\t Stack height changed by unevalled add/sub: bottom\n");
1581    }
1582 }
1583
1584 void StackAnalysis::handlePowerStoreUpdate(Instruction::Ptr insn,
1585    TransferFuncs &xferFuncs) {
1586
1587    if (!insn->isWritten(theStackPtr)) {
1588       return handleDefault(insn, xferFuncs);
1589    }
1590    
1591    std::set<Expression::Ptr> memWriteAddrs;
1592    insn->getMemoryWriteOperands(memWriteAddrs);
1593    Expression::Ptr stackWrite = *(memWriteAddrs.begin());
1594    stackanalysis_printf("\t\t\t ...checking operand %s\n",
1595       stackWrite->format().c_str());
1596    stackanalysis_printf("\t\t\t ...binding %s to 0\n",
1597       theStackPtr->format().c_str());
1598    stackWrite->bind(theStackPtr.get(), Result(u32, 0));
1599    Result res = stackWrite->eval();
1600    Absloc sploc(sp());
1601    if (res.defined) {
1602       long delta = res.convert<long>();
1603       xferFuncs.push_back(TransferFunc::deltaFunc(sploc, delta));
1604       copyBaseSubReg(sp(), xferFuncs);
1605       stackanalysis_printf(
1606          "\t\t\t Stack height changed by evalled stwu: %lx\n", delta);
1607    } else {
1608       xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1609       bottomBaseSubReg(sp(), xferFuncs);
1610       stackanalysis_printf(
1611          "\t\t\t Stack height changed by unevalled stwu: bottom\n");
1612    }
1613 }
1614
1615
1616 void StackAnalysis::handleMov(Instruction::Ptr insn, Block *block,
1617    const Offset off, TransferFuncs &xferFuncs) {
1618    // Some cases:
1619    //   1. mov reg, reg
1620    //   2. mov imm, reg
1621    //   3. mov mem, reg
1622    //   4. mov reg, mem
1623    //   5. mov imm, mem
1624    // 
1625    // #1 Causes register copying.
1626    // #2 Causes an absolute value in the register.
1627    // #3 Depends on whether the memory address we're loading from can be
1628    //    determined statically.
1629    //    a. If it can, we copy the register to the memory location we're
1630    //       loading from.
1631    //    b. Otherwise, we set the register to TOP.  Note that this is safe
1632    //       since StackMod fails whenever a stack height is written out to an
1633    //       undetermined (topped) location.
1634    // #4 Depends on whether the address we're storing to can be determined
1635    //    statically.
1636    //    a. If it can, we copy the memory address to the register.
1637    //    b. Otherwise, we ignore the store.
1638    // #5 Depends on whether the address we're storing to can be determined
1639    //    statically.
1640    //    a. If it can, we give the address an absolute value.
1641    //    b. Otherwise, we ignore the store.
1642
1643    Architecture arch = insn->getArch();  // Needed for debug messages
1644
1645    // Extract operands
1646    std::vector<Operand> operands;
1647    insn->getOperands(operands);
1648    assert(operands.size() == 2);
1649
1650    // Extract written/read register sets
1651    std::set<RegisterAST::Ptr> writtenRegs;
1652    std::set<RegisterAST::Ptr> readRegs;
1653    operands[0].getWriteSet(writtenRegs);
1654    operands[1].getReadSet(readRegs);
1655
1656
1657    if (insn->writesMemory()) {
1658       assert(writtenRegs.size() == 0);
1659       stackanalysis_printf("\t\t\tMemory write to: %s\n",
1660          operands[0].format(arch).c_str());
1661
1662       // Extract the expression inside the dereference
1663       std::vector<Expression::Ptr> addrExpr;
1664       operands[0].getValue()->getChildren(addrExpr);
1665       assert(addrExpr.size() == 1);
1666
1667       // Try to determine the written memory address
1668       Absloc writtenLoc;
1669       StateEvalVisitor visitor;
1670       if (intervals_ == NULL) {
1671          visitor = StateEvalVisitor(off, insn, NULL);
1672       } else {
1673          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1674       }
1675       addrExpr[0]->apply(&visitor);
1676       if (visitor.isDefined()) {
1677          std::pair<Address, bool> resultPair = visitor.getResult();
1678          if (resultPair.second) {
1679             // We have a stack slot
1680             writtenLoc = Absloc(resultPair.first, 0, NULL);
1681          } else {
1682             // We have a static address
1683             writtenLoc = Absloc(resultPair.first);
1684          }
1685          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1686             writtenLoc.format().c_str());
1687       } else {
1688          // Cases 4b and 5b
1689          stackanalysis_printf("\t\t\tCan't determine location\n");
1690          return;
1691       }
1692
1693       if (readRegs.size() > 0) {
1694          // Case 4a
1695          assert(readRegs.size() == 1);
1696          Absloc from((*readRegs.begin())->getID());
1697          xferFuncs.push_back(TransferFunc::copyFunc(from, writtenLoc));
1698       } else {
1699          // Case 5a
1700          Expression::Ptr immExpr = operands[1].getValue();
1701          assert(typeid(*immExpr) == typeid(Immediate));
1702          long immVal = immExpr->eval().convert<long>();
1703          xferFuncs.push_back(TransferFunc::absFunc(writtenLoc, immVal));
1704       }
1705       return;
1706    }
1707
1708
1709    // Only Cases 1, 2, and 3 can reach this point.
1710    // As a result, we know there's exactly one written register.
1711    assert(writtenRegs.size() == 1);
1712    MachRegister written = (*writtenRegs.begin())->getID();
1713    Absloc writtenLoc(written);
1714
1715    if (insn->readsMemory()) {
1716       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1717          operands[1].format(arch).c_str());
1718
1719       // Extract the expression inside the dereference
1720       std::vector<Expression::Ptr> addrExpr;
1721       operands[1].getValue()->getChildren(addrExpr);
1722       assert(addrExpr.size() == 1);
1723
1724       // Try to determine the read memory address
1725       StateEvalVisitor visitor;
1726       if (intervals_ == NULL) {
1727          visitor = StateEvalVisitor(off, insn, NULL);
1728       } else {
1729          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1730       }
1731       addrExpr[0]->apply(&visitor);
1732       if (visitor.isDefined()) {
1733          // Case 3a
1734          std::pair<Address, bool> resultPair = visitor.getResult();
1735          Absloc readLoc;
1736          if (resultPair.second) {
1737             // We have a stack slot
1738             readLoc = Absloc(resultPair.first, 0, NULL);
1739          } else {
1740             // We have a static address
1741             readLoc = Absloc(resultPair.first);
1742          }
1743          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1744             readLoc.format().c_str());
1745          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1746          copyBaseSubReg(written, xferFuncs);
1747       } else {
1748          // Case 3b
1749          stackanalysis_printf("\t\t\tCan't determine location\n");
1750          xferFuncs.push_back(TransferFunc::retopFunc(writtenLoc));
1751          retopBaseSubReg(written, xferFuncs);
1752       }
1753       return;
1754    }
1755
1756
1757    // Only Cases 1 and 2 can reach this point.
1758    // As a result, we know there's either 0 or 1 read registers
1759    MachRegister read;
1760    if (!readRegs.empty()) {
1761       assert(readRegs.size() == 1);
1762       read = (*readRegs.begin())->getID();
1763    }
1764    Absloc readLoc(read);
1765
1766
1767    if (read.isValid()) {
1768       // Case 1
1769       stackanalysis_printf("\t\t\tCopy detected: %s -> %s\n",
1770          read.name().c_str(), written.name().c_str());
1771       xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1772       copyBaseSubReg(written, xferFuncs);
1773    } else {
1774       // Case 2
1775       InstructionAPI::Expression::Ptr readExpr = operands[1].getValue();
1776       assert(typeid(*readExpr) == typeid(InstructionAPI::Immediate));
1777       long readValue = readExpr->eval().convert<long>();
1778       stackanalysis_printf("\t\t\tImmediate to register move: %s set to %ld\n",
1779          written.name().c_str(), readValue);
1780       xferFuncs.push_back(TransferFunc::absFunc(writtenLoc, readValue));
1781       retopBaseSubReg(written, xferFuncs);
1782    }
1783 }
1784
1785 void StackAnalysis::handleZeroExtend(Instruction::Ptr insn, Block *block,
1786    const Offset off, TransferFuncs &xferFuncs) {
1787    // In x86/x86_64, zero extends can't write to memory
1788    assert(!insn->writesMemory());
1789
1790    Architecture arch = insn->getArch();  // Needed for debug messages
1791
1792    // Extract operands
1793    std::vector<Operand> operands;
1794    insn->getOperands(operands);
1795    assert(operands.size() == 2);
1796
1797    // Extract written/read register sets
1798    std::set<RegisterAST::Ptr> writtenRegs;
1799    std::set<RegisterAST::Ptr> readRegs;
1800    operands[0].getWriteSet(writtenRegs);
1801    operands[1].getReadSet(readRegs);
1802
1803    assert(writtenRegs.size() == 1);
1804    const MachRegister &written = (*writtenRegs.begin())->getID();
1805    Absloc writtenLoc(written);
1806
1807    // Handle memory loads
1808    if (insn->readsMemory()) {
1809       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1810          operands[1].format(arch).c_str());
1811
1812       // Extract the expression inside the dereference
1813       std::vector<Expression::Ptr> addrExpr;
1814       operands[1].getValue()->getChildren(addrExpr);
1815       assert(addrExpr.size() == 1);
1816
1817       // Try to determine the read memory address
1818       StateEvalVisitor visitor;
1819       if (intervals_ == NULL) {
1820          visitor = StateEvalVisitor(off, insn, NULL);
1821       } else {
1822          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1823       }
1824       addrExpr[0]->apply(&visitor);
1825       if (visitor.isDefined()) {
1826          // We can track the memory location we're loading from
1827          std::pair<Address, bool> resultPair = visitor.getResult();
1828          Absloc readLoc;
1829          if (resultPair.second) {
1830             // We have a stack slot
1831             readLoc = Absloc(resultPair.first, 0, NULL);
1832          } else {
1833             // We have a static address
1834             readLoc = Absloc(resultPair.first);
1835          }
1836          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1837             readLoc.format().c_str());
1838          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1839          copyBaseSubReg(written, xferFuncs);
1840       } else {
1841          // We can't track this memory location
1842          stackanalysis_printf("\t\t\tCan't determine location\n");
1843          xferFuncs.push_back(TransferFunc::retopFunc(writtenLoc));
1844          retopBaseSubReg(written, xferFuncs);
1845       }
1846       return;
1847    }
1848
1849    assert(readRegs.size() == 1);
1850    Absloc readLoc((*readRegs.begin())->getID());
1851
1852    stackanalysis_printf("\t\t\tCopy detected: %s -> %s\n",
1853       readLoc.format().c_str(), writtenLoc.format().c_str());
1854    xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1855    copyBaseSubReg(written, xferFuncs);
1856 }
1857
1858 void StackAnalysis::handleSignExtend(Instruction::Ptr insn, Block *block,
1859    const Offset off, TransferFuncs &xferFuncs) {
1860    // This instruction sign extends the read register into the written
1861    // register. Copying insn't really correct here...sign extension is going
1862    // to change the value...
1863
1864    // In x86/x86_64, sign extends can't write to memory
1865    assert(!insn->writesMemory());
1866
1867    Architecture arch = insn->getArch();  // Needed for debug messages
1868
1869    // Extract operands
1870    std::vector<Operand> operands;
1871    insn->getOperands(operands);
1872    assert(operands.size() == 2);
1873
1874    // Extract written/read register sets
1875    std::set<RegisterAST::Ptr> writtenRegs;
1876    std::set<RegisterAST::Ptr> readRegs;
1877    operands[0].getWriteSet(writtenRegs);
1878    operands[1].getReadSet(readRegs);
1879
1880    assert(writtenRegs.size() == 1);
1881    const MachRegister &written = (*writtenRegs.begin())->getID();
1882    Absloc writtenLoc(written);
1883
1884    // Handle memory loads
1885    if (insn->readsMemory()) {
1886       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1887          operands[1].format(arch).c_str());
1888
1889       // Extract the expression inside the dereference
1890       std::vector<Expression::Ptr> addrExpr;
1891       operands[1].getValue()->getChildren(addrExpr);
1892       assert(addrExpr.size() == 1);
1893
1894       // Try to determine the read memory address
1895       StateEvalVisitor visitor;
1896       if (intervals_ == NULL) {
1897          visitor = StateEvalVisitor(off, insn, NULL);
1898       } else {
1899          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1900       }
1901       addrExpr[0]->apply(&visitor);
1902       if (visitor.isDefined()) {
1903          // We can track the memory location we're loading from
1904          std::pair<Address, bool> resultPair = visitor.getResult();
1905          Absloc readLoc;
1906          if (resultPair.second) {
1907             // We have a stack slot
1908             readLoc = Absloc(resultPair.first, 0, NULL);
1909          } else {
1910             // We have a static address
1911             readLoc = Absloc(resultPair.first);
1912          }
1913          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1914             readLoc.format().c_str());
1915          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc,
1916             true));
1917          copyBaseSubReg(written, xferFuncs);
1918       } else {
1919          // We can't track this memory location
1920          stackanalysis_printf("\t\t\tCan't determine location\n");
1921          xferFuncs.push_back(TransferFunc::retopFunc(writtenLoc));
1922          retopBaseSubReg(written, xferFuncs);
1923       }
1924       return;
1925    }
1926
1927    assert(readRegs.size() == 1);
1928    Absloc readLoc((*readRegs.begin())->getID());
1929
1930    stackanalysis_printf(
1931       "\t\t\t Sign extend insn detected: %s -> %s (must be top or bottom)\n",
1932       readLoc.format().c_str(), writtenLoc.format().c_str());
1933    xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc, true));
1934    copyBaseSubReg(written, xferFuncs);
1935 }
1936
1937 void StackAnalysis::handleSpecialSignExtend(Instruction::Ptr insn,
1938    TransferFuncs &xferFuncs) {
1939    // This instruction sign extends the read register into the written
1940    // register. Copying insn't really correct here...sign extension is going
1941    // to change the value...
1942
1943    // Extract written/read register sets
1944    std::set<RegisterAST::Ptr> writtenRegs;
1945    insn->getWriteSet(writtenRegs);
1946    assert(writtenRegs.size() == 1);
1947    MachRegister writtenReg = (*writtenRegs.begin())->getID();
1948    MachRegister readReg;
1949    if (writtenReg == x86_64::rax) readReg = x86_64::eax;
1950    else if (writtenReg == x86_64::eax) readReg = x86_64::ax;
1951    else if (writtenReg == x86_64::ax) readReg = x86_64::al;
1952    else if (writtenReg == x86::eax) readReg = x86::ax;
1953    else if (writtenReg == x86::ax) readReg = x86::al;
1954    else assert(false);
1955
1956    Absloc writtenLoc(writtenReg);
1957    Absloc readLoc(readReg);
1958
1959    stackanalysis_printf(
1960       "\t\t\t Special sign extend detected: %s -> %s (must be top/bottom)\n",
1961       readLoc.format().c_str(), writtenLoc.format().c_str());
1962    xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc, true));
1963    copyBaseSubReg(writtenReg, xferFuncs);
1964 }
1965
1966 void StackAnalysis::handleDefault(Instruction::Ptr insn,
1967    TransferFuncs &xferFuncs) {
1968    std::set<RegisterAST::Ptr> written;
1969    insn->getWriteSet(written);
1970    for (auto iter = written.begin(); iter != written.end(); ++iter) {
1971       const MachRegister &reg = (*iter)->getID();
1972       if ((signed int) reg.regClass() == x86::FLAG ||
1973          (signed int) reg.regClass() == x86_64::FLAG) {
1974          continue;
1975       }
1976       Absloc loc(reg);
1977       xferFuncs.push_back(TransferFunc::copyFunc(loc, loc, true));
1978       copyBaseSubReg(reg, xferFuncs);
1979       stackanalysis_printf(
1980          "\t\t\t Unhandled insn %s detected: %s set to topBottom\n",
1981          insn->format().c_str(), (*iter)->getID().name().c_str());
1982    }
1983 }
1984
1985 bool StackAnalysis::isCall(Instruction::Ptr insn) {
1986    return insn->getCategory() == c_CallInsn;
1987 }
1988
1989 bool StackAnalysis::handleNormalCall(Instruction::Ptr insn, Block *block,
1990    Offset off, TransferFuncs &xferFuncs) {
1991
1992    if (!insn->getControlFlowTarget()) return false;
1993
1994    // Must be a thunk based on parsing.
1995    if (off != block->lastInsnAddr()) return false;
1996    
1997    // Top caller-save registers
1998    // Bottom return registers
1999    ABI* abi = ABI::getABI(word_size);
2000    const bitArray callWritten = abi->getCallWrittenRegisters();
2001    const bitArray returnRegs = abi->getReturnRegisters();
2002    for (auto iter = abi->getIndexMap()->begin();
2003         iter != abi->getIndexMap()->end();
2004         ++iter) {
2005        // We only care about GPRs right now
2006       unsigned int gpr;
2007       Architecture arch = insn->getArch();
2008       switch(arch) {
2009          case Arch_x86:
2010             gpr = x86::GPR;
2011             break;
2012          case Arch_x86_64:
2013             gpr = x86_64::GPR;
2014             break;
2015          case Arch_ppc32:
2016             gpr = ppc32::GPR;
2017             break;
2018          case Arch_ppc64:
2019             gpr = ppc64::GPR;
2020             break;
2021          default:
2022             handleDefault(insn, xferFuncs);
2023             return true;
2024       }
2025       if ((*iter).first.regClass() == gpr) {
2026          if (callWritten.test((*iter).second)) {
2027             Absloc loc((*iter).first);
2028             if (returnRegs.test((*iter).second)) {
2029                // Bottom
2030                xferFuncs.push_back(TransferFunc::bottomFunc(loc));
2031                bottomBaseSubReg(iter->first, xferFuncs);
2032             } else {
2033                // Top
2034                xferFuncs.push_back(TransferFunc::retopFunc(loc));
2035                retopBaseSubReg(iter->first, xferFuncs);
2036             }
2037          }
2038       }
2039    }
2040
2041    const Block::edgelist &outs = block->targets();
2042    for (auto eit = outs.begin(); eit != outs.end(); ++eit) {
2043       Edge *cur_edge = (Edge*)*eit;
2044
2045       Absloc sploc(sp());
2046
2047       if (cur_edge->type() == DIRECT) {
2048          // For some reason we're treating this
2049          // call as a branch. So it shifts the stack
2050          // like a push (heh) and then we're done.
2051          stackanalysis_printf(
2052             "\t\t\t Stack height changed by simulate-jump call\n");
2053          xferFuncs.push_back(TransferFunc::deltaFunc(sploc, -1 * word_size));
2054          copyBaseSubReg(sp(), xferFuncs);
2055          return true;
2056       }
2057       
2058       if (cur_edge->type() != CALL) continue;
2059       
2060       Block *target_bbl = cur_edge->trg();
2061       Function *target_func = target_bbl->obj()->findFuncByEntry(
2062          target_bbl->region(), target_bbl->start());
2063       
2064       if (!target_func) continue;
2065       
2066       Height h = getStackCleanAmount(target_func);
2067       if (h == Height::bottom) {
2068          stackanalysis_printf(
2069             "\t\t\t Stack height changed by self-cleaning function: bottom\n");
2070          xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
2071          bottomBaseSubReg(sp(), xferFuncs);
2072       } else {
2073          stackanalysis_printf(
2074             "\t\t\t Stack height changed by self-cleaning function: %ld\n",
2075             h.height());
2076          xferFuncs.push_back(TransferFunc::deltaFunc(sploc, h.height()));
2077          copyBaseSubReg(sp(), xferFuncs);
2078       }
2079       return true;
2080
2081    }
2082    stackanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
2083    return true;
2084 }
2085                                        
2086
2087 bool StackAnalysis::handleThunkCall(Instruction::Ptr insn,
2088    TransferFuncs &xferFuncs) {
2089
2090    // We know that we're not a normal call, so it depends on whether the CFT is
2091    // "next instruction" or not.
2092    if (insn->getCategory() != c_CallInsn || !insn->getControlFlowTarget()) {
2093       return false;
2094    }
2095
2096    // Eval of getCFT(0) == size?
2097    Expression::Ptr cft = insn->getControlFlowTarget();
2098    cft->bind(thePC.get(), Result(u32, 0));
2099    Result res = cft->eval();
2100    if (!res.defined) return false;
2101    if (res.convert<unsigned>() == insn->size()) {
2102       Absloc sploc(sp());
2103       xferFuncs.push_back(TransferFunc::deltaFunc(sploc, -1 * word_size));
2104       copyBaseSubReg(sp(), xferFuncs);
2105       return true;
2106    }
2107    // Else we're calling a mov, ret thunk that has no effect on the stack
2108    // pointer
2109    return true;
2110 }
2111
2112
2113 void StackAnalysis::createEntryInput(AbslocState &input) {
2114    // FIXME for POWER/non-IA32
2115    // IA32 - the in height includes the return address and therefore
2116    // is <wordsize>
2117    // POWER - the in height is 0
2118 #if defined(arch_power)
2119    input[Absloc(sp())] = Height(0);
2120 #elif (defined(arch_x86) || defined(arch_x86_64))
2121    input[Absloc(sp())] = Height(-1 * word_size);
2122    if (sp() == x86_64::rsp) input[Absloc(x86_64::esp)] = Height(-word_size);
2123 #else
2124    assert(0 && "Unimplemented architecture");
2125 #endif
2126 }
2127
2128 void StackAnalysis::createSummaryEntryInput(TransferSet &input) {
2129    // Get a set of all input locations
2130    std::set<Absloc> inputLocs;
2131    for (auto beIter = blockEffects->begin(); beIter != blockEffects->end();
2132       beIter++) {
2133       const SummaryFunc &sf = beIter->second;
2134       const TransferSet &af = sf.accumFuncs;
2135       for (auto afIter = af.begin(); afIter != af.end(); afIter++) {
2136          const TransferFunc &tf = afIter->second;
2137          if (tf.target.isValid()) {
2138             inputLocs.insert(tf.target);
2139          }
2140          if (tf.from.isValid()) {
2141             inputLocs.insert(tf.from);
2142          }
2143          if (!tf.fromRegs.empty()) {
2144             for (auto frIter = tf.fromRegs.begin(); frIter != tf.fromRegs.end();
2145                frIter++) {
2146                Absloc deploc = frIter->first;
2147                inputLocs.insert(deploc);
2148             }
2149          }
2150       }
2151    }
2152
2153    // Create identity functions for each input location
2154    for (auto locIter = inputLocs.begin(); locIter != inputLocs.end();
2155       locIter++) {
2156       const Absloc &loc = *locIter;
2157       input[loc] = TransferFunc::identityFunc(loc);
2158    }
2159 }
2160
2161
2162 StackAnalysis::AbslocState StackAnalysis::getSrcOutputLocs(Edge* e) {
2163    Block* b = e->src();
2164    stackanalysis_printf("%lx ", b->lastInsnAddr());
2165    return blockOutputs[b];
2166 }
2167
2168 StackAnalysis::TransferSet StackAnalysis::getSummarySrcOutputLocs(Edge* e) {
2169    Block* b = e->src();
2170    stackanalysis_printf("%lx ", b->lastInsnAddr());
2171    return blockSummaryOutputs[b];
2172 }
2173
2174 void StackAnalysis::meetInputs(Block *block, AbslocState& blockInput,
2175    AbslocState &input) {
2176
2177    input.clear();
2178
2179    //Intraproc epred; // ignore calls, returns in edge iteration
2180    //NoSinkPredicate epred2(&epred); // ignore sink node (unresolvable)
2181    intra_nosink epred2;
2182
2183    stackanalysis_printf("\t ... In edges: ");
2184    const Block::edgelist & inEdges = block->sources();
2185    std::for_each(
2186       boost::make_filter_iterator(epred2, inEdges.begin(), inEdges.end()),
2187       boost::make_filter_iterator(epred2, inEdges.end(), inEdges.end()),
2188       boost::bind(&StackAnalysis::meet, this,
2189          boost::bind(&StackAnalysis::getSrcOutputLocs, this, _1),
2190          boost::ref(input)));
2191    stackanalysis_printf("\n");
2192
2193    meet(blockInput, input);
2194 }
2195
2196
2197 void StackAnalysis::meetSummaryInputs(Block *block, TransferSet &blockInput,
2198    TransferSet &input) {
2199
2200    input.clear();
2201
2202    //Intraproc epred; // ignore calls, returns in edge iteration
2203    //NoSinkPredicate epred2(&epred); // ignore sink node (unresolvable)
2204    intra_nosink epred2;
2205
2206    stackanalysis_printf("\t ... In edges: ");
2207    const Block::edgelist & inEdges = block->sources();
2208    std::for_each(
2209       boost::make_filter_iterator(epred2, inEdges.begin(), inEdges.end()),
2210       boost::make_filter_iterator(epred2, inEdges.end(), inEdges.end()),
2211       boost::bind(&StackAnalysis::meetSummary, this,
2212          boost::bind(&StackAnalysis::getSummarySrcOutputLocs, this, _1),
2213          boost::ref(input)));
2214    stackanalysis_printf("\n");
2215
2216    meetSummary(blockInput, input);
2217 }
2218
2219 void StackAnalysis::meet(const AbslocState &input, AbslocState &accum) {
2220    for (AbslocState::const_iterator iter = input.begin();
2221       iter != input.end(); ++iter) {
2222       accum[iter->first] = Height::meet(iter->second, accum[iter->first]);
2223       if (accum[iter->first].isTop()) {
2224          accum.erase(iter->first);
2225       }
2226    }
2227 }
2228
2229
2230 void StackAnalysis::meetSummary(const TransferSet &input, TransferSet &accum) {
2231    for (auto iter = input.begin(); iter != input.end(); ++iter) {
2232       const Absloc &loc = iter->first;
2233       const TransferFunc &inputFunc = iter->second;
2234       accum[loc] = TransferFunc::meet(inputFunc, accum[loc]);
2235       if (accum[loc].isTop() && !accum[loc].isRetop()) {
2236          accum.erase(loc);
2237       }
2238    }
2239 }
2240
2241
2242 StackAnalysis::Height &StackAnalysis::Height::operator+=(const Height &other) {
2243    if (isBottom()) return *this;
2244    if (other.isBottom()) {
2245       *this = bottom;
2246       return *this;
2247    }
2248    if (isTop() && other.isTop()) {
2249       // TOP + TOP = TOP
2250       *this = top;
2251       return *this;
2252    }
2253    if (isTop() || other.isTop()) {
2254       // TOP + height = BOTTOM
2255       *this = bottom;
2256       return *this;
2257    }
2258
2259    height_ += other.height_;
2260    return *this;
2261 }
2262
2263 StackAnalysis::Height &StackAnalysis::Height::operator+=(
2264    const signed long &rhs) {
2265    if (isBottom()) return *this;
2266    if (isTop()) return *this;
2267
2268    height_ += rhs;
2269    return *this;
2270 }
2271
2272 const StackAnalysis::Height StackAnalysis::Height::operator+(const Height &rhs)
2273    const {
2274    if (isBottom()) return bottom;
2275    if (rhs.isBottom()) return rhs;
2276    if (isTop() && rhs.isTop()) return top;
2277    if (isTop() || rhs.isTop()) return bottom;
2278    return Height(height_ + rhs.height_);
2279 }
2280
2281 const StackAnalysis::Height StackAnalysis::Height::operator+(
2282    const signed long &rhs) const {
2283    if (isBottom()) return bottom;
2284    if (isTop()) return top;
2285    return Height(height_ + rhs);
2286 }
2287
2288 const StackAnalysis::Height StackAnalysis::Height::operator-(const Height &rhs)
2289    const {
2290    if (isBottom()) return bottom;
2291    if (rhs.isBottom()) return rhs;
2292    if (isTop() && rhs.isTop()) return top;
2293    if (isTop() || rhs.isTop()) return bottom;
2294    return Height(height_ - rhs.height_);
2295 }
2296
2297
2298 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::identityFunc(
2299    Absloc r) {
2300    return copyFunc(r, r);
2301 }
2302
2303 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::deltaFunc(Absloc r,
2304    long d) {
2305    return TransferFunc(uninitialized, d, r, r);
2306 }
2307
2308 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::absFunc(Absloc r,
2309    long a, bool i) {
2310    return TransferFunc(a, 0, Absloc(), r, i);
2311 }
2312
2313 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::copyFunc(Absloc f,
2314    Absloc t, bool i) {
2315    return TransferFunc (uninitialized, 0, f, t, i);
2316 }
2317
2318 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::bottomFunc(Absloc r) {
2319    return TransferFunc(notUnique, notUnique, Absloc(), r, false, false, BOTTOM);
2320 }
2321
2322 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::retopFunc(Absloc r) {
2323    return TransferFunc(uninitialized, 0, Absloc(), r, false, true, TOP);
2324 }
2325
2326 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::sibFunc(
2327    std::map<Absloc, std::pair<long,bool> > f, long d, Absloc t) {
2328    return TransferFunc(f, d, t);
2329 }
2330
2331 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::meet(
2332    const TransferFunc &lhs, const TransferFunc &rhs) {
2333    // Handle default-constructed TransferFuncs
2334    if (lhs.isTop() && !lhs.isRetop()) return rhs;
2335    if (rhs.isTop() && !rhs.isRetop()) return lhs;
2336
2337    assert(lhs.target == rhs.target);
2338    if (lhs == rhs) return lhs;
2339
2340    TransferFunc ret;
2341    if (lhs.isAbs()) {
2342       if (rhs.isAbs()) {
2343          // Since we know lhs != rhs, the abs values must be different
2344          ret = retopFunc(lhs.target);
2345       } else if (rhs.isCopy() || rhs.isBottom() || rhs.isRetop() ||
2346          rhs.isSIB()) {
2347          ret = rhs;
2348       } else {
2349          assert(false);
2350       }
2351    } else if (lhs.isCopy()) {
2352       if (rhs.isAbs()) {
2353          ret = lhs;
2354       } else if (rhs.isCopy()) {
2355          if (lhs.from == rhs.from) {
2356             // Same base register. Since we know lhs != rhs, either the deltas
2357             // are different or the topBottom values are different. Either way,
2358             // we need to return a function that is topBottom.
2359             ret = lhs;
2360             ret.topBottom = true;
2361             ret.delta = 0;
2362          } else {
2363             // Different base registers.  Use a SIB function to capture both
2364             // possible bases.  Note that current SIB function handling doesn't
2365             // actually add the terms together.
2366             // FIXME if SIB function handling changes.
2367             std::map<Absloc, std::pair<long, bool>> fromRegs;
2368             fromRegs[lhs.from] = std::make_pair(1, true);
2369             fromRegs[rhs.from] = std::make_pair(1, true);
2370             ret = sibFunc(fromRegs, 0, lhs.target);
2371          }
2372       } else if (rhs.isBottom()) {
2373          ret = rhs;
2374       } else if (rhs.isRetop()) {
2375          ret = lhs;
2376       } else if (rhs.isSIB()) {
2377          // Add the source register of the LHS copy to the RHS SIB function.
2378          // Note that current SIB function handling doesn't actually add the
2379          // terms together.
2380          // FIXME if SIB function handling changes.
2381          ret = rhs;
2382          ret.fromRegs[lhs.from] = std::make_pair(1, true);
2383       } else {
2384          assert(false);
2385       }
2386    } else if (lhs.isBottom()) {
2387       ret = lhs;
2388    } else if (lhs.isRetop()) {
2389       if (rhs.isAbs()) {
2390          ret = lhs;
2391       } else if (rhs.isCopy() || rhs.isBottom() || rhs.isRetop() ||
2392          rhs.isSIB()) {
2393          ret = rhs;
2394       } else {
2395          assert(false);
2396       }
2397    } else if (lhs.isSIB()) {
2398       if (rhs.isAbs()) {
2399          ret = lhs;
2400       } else if (rhs.isCopy()) {
2401          // Add the source register of the RHS copy to the LHS SIB function.
2402          // Note that current SIB function handling doesn't actually add the
2403          // terms together.
2404          // FIXME if SIB function handling changes.
2405          ret = lhs;
2406          ret.fromRegs[rhs.from] = std::make_pair(1, true);
2407       } else if (rhs.isBottom()) {
2408          ret = rhs;
2409       } else if (rhs.isRetop()) {
2410          ret = lhs;
2411       } else if (rhs.isSIB()) {
2412          if (lhs.fromRegs == rhs.fromRegs) {
2413             // Same SIB.  Since we know lhs != rhs, either the deltas are
2414             // different or the topBottom values are different.  Either way, we
2415             // need to return a function that is topBottom.
2416             ret = lhs;
2417             ret.topBottom = true;
2418             ret.delta = 0;
2419          } else {
2420             // Different SIBs.  Combine the terms of the LHS and RHS SIB
2421             // functions.  Note that current SIB function handling doesn't
2422             // actually add the terms together.
2423             // FIXME if SIB function handling changes.
2424             ret = lhs;
2425             for (auto iter = rhs.fromRegs.begin(); iter != rhs.fromRegs.end();
2426                iter++) {
2427                const Absloc &loc = iter->first;
2428                const std::pair<long, bool> &val = iter->second;
2429                auto findLoc = ret.fromRegs.find(loc);
2430                if (findLoc == ret.fromRegs.end() || (val.first == 1 &&
2431                   ret.fromRegs[loc].first != 1)) {
2432                   ret.fromRegs[loc] = val;
2433                }
2434             }
2435          }
2436       } else {
2437          assert(false);
2438       }
2439    } else {
2440       assert(false);
2441    }
2442    return ret;
2443 }
2444
2445
2446 bool StackAnalysis::TransferFunc::isIdentity() const {
2447    return isCopy() && from == target && delta == 0 && !topBottom;
2448 }
2449
2450 bool StackAnalysis::TransferFunc::isBottom() const {
2451    return type_ == BOTTOM;
2452 }
2453
2454 bool StackAnalysis::TransferFunc::isTop() const {
2455    return type_ == TOP;
2456 }
2457
2458 bool StackAnalysis::TransferFunc::isRetop() const {
2459    return isTop() && retop;
2460 }
2461
2462 bool StackAnalysis::TransferFunc::isCopy() const {
2463    return from.isValid();
2464 }
2465
2466 bool StackAnalysis::TransferFunc::isAbs() const {
2467    return !isTop() && !isBottom() && !isCopy() && !isSIB();
2468 }
2469
2470 bool StackAnalysis::TransferFunc::isDelta() const {
2471    return delta != 0;
2472 }
2473
2474 bool StackAnalysis::TransferFunc::isSIB() const {
2475     return (fromRegs.size() > 0);
2476 }
2477
2478
2479 // Destructive update of the input map. Assumes inputs are absolute,
2480 // uninitialized, or bottom; no deltas.
2481 StackAnalysis::Height StackAnalysis::TransferFunc::apply(
2482    const AbslocState &inputs) const {
2483    assert(target.isValid());
2484    // Bottom stomps everything
2485    if (isBottom()) {
2486       return Height::bottom;
2487    }
2488
2489    AbslocState::const_iterator iter = inputs.find(target);
2490    Height input;
2491    if (iter != inputs.end()) {
2492       input = iter->second;
2493    } else {
2494       input = Height::top;
2495    }
2496
2497    bool isTopBottomOrig = isTopBottom();
2498
2499    if (isSIB()) {
2500       input = Height::top; // SIB overwrites, so start at TOP
2501       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
2502          Absloc curLoc = (*iter).first;
2503          long curScale = (*iter).second.first;
2504          bool curTopBottom = (*iter).second.second;
2505          auto findLoc = inputs.find(curLoc);
2506          Height locInput;
2507          if (findLoc == inputs.end()) {
2508             locInput = Height::top;
2509          } else {
2510             locInput = findLoc->second;
2511          }
2512
2513          if (locInput == Height::top) {
2514             // This term doesn't affect our end result, so it can be safely
2515             // ignored.
2516          } else if (locInput == Height::bottom) {
2517             if (curScale == 1) {
2518                // Must bottom everything only if the scale is 1.  Otherwise,
2519                // any stack height will be obfuscated.
2520                input = Height::bottom;
2521                break;
2522             }
2523          } else {
2524             if (curScale == 1) {
2525                // If the scale isn't 1, then any stack height is obfuscated,
2526                // and we can safely ignore the term.
2527                if (curTopBottom) {
2528                   input = Height::bottom;
2529                   break;
2530                } else {
2531                   input += locInput; // Matt: Always results in bottom?
2532                }
2533             }
2534          }
2535       }
2536    }
2537
2538    if (isAbs()) {
2539       // We cannot be a copy, as the absolute removes that.
2540       assert(!isCopy());
2541       // Apply the absolute
2542       // NOTE: an absolute is not a stack height, set input to top
2543       //input = abs;
2544       input = Height::top;
2545    }
2546    if (isCopy()) {
2547       // Cannot be absolute
2548       assert(!isAbs());
2549       // Copy the input value from whatever we're a copy of.
2550       AbslocState::const_iterator iter2 = inputs.find(from);
2551       if (iter2 != inputs.end()) input = iter2->second;
2552       else input = Height::top;
2553    }
2554    if (isDelta()) {
2555       input += delta;
2556    }
2557    if (isRetop()) {
2558       input = Height::top;
2559    }
2560    if (isTopBottomOrig) {
2561       if (!input.isTop()) {
2562          input = Height::bottom;
2563       }
2564    }
2565    return input;
2566 }
2567
2568 // Returns accumulated transfer function without modifying inputs
2569 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::summaryAccumulate(
2570    const TransferSet &inputs) const {
2571    TransferFunc input;
2572    auto findTarget = inputs.find(target);
2573    if (findTarget != inputs.end()) {
2574       input = findTarget->second;
2575    }
2576    if (input.target.isValid()) assert(input.target == target);
2577    input.target = target; // Default constructed TransferFuncs won't have this
2578    assert(target.isValid());
2579
2580    // Bottom stomps everything
2581    if (isBottom()) {
2582       input = bottomFunc(target);
2583       return input;
2584    }
2585    bool isTopBottomOrig = isTopBottom();
2586    if (!input.isTopBottom() && !input.isRetop()) {
2587       input.topBottom = isTopBottomOrig;
2588    }
2589    // Absolutes override everything else
2590    if (isAbs()) {
2591       input = absFunc(target, abs, false);
2592       return input;
2593    }
2594    if (isSIB()) {
2595       // First check for special cases
2596       bool allAbs = true;
2597       bool allToppable = true;
2598       bool anyBottomed = false;
2599       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); iter++) {
2600          Absloc fromLocOrig = iter->first;
2601          long scaleOrig = iter->second.first;
2602          auto inputEntry = inputs.find(fromLocOrig);
2603          if (inputEntry == inputs.end()) {
2604             allAbs = false;
2605             if (scaleOrig == 1) {
2606                allToppable = false;
2607             }
2608          } else {
2609             if (inputEntry->second.isBottom() && scaleOrig == 1) {
2610                anyBottomed = true;
2611             }
2612             if (!inputEntry->second.isRetop() && !inputEntry->second.isAbs() &&
2613                scaleOrig == 1) {
2614                allToppable = false;
2615             }
2616             if (!inputEntry->second.isAbs()) {
2617                allAbs = false;
2618             }
2619          }
2620       }
2621
2622       // Now handle special cases
2623       if (anyBottomed) {
2624          input = bottomFunc(target);
2625          return input;
2626       }
2627       if (allAbs) {
2628          long newDelta = delta;
2629          for (auto iter = fromRegs.begin(); iter != fromRegs.end(); iter++) {
2630             Absloc fromLocOrig = iter->first;
2631             long scaleOrig = iter->second.first;
2632             TransferFunc inputAbsFunc = inputs.find(fromLocOrig)->second;
2633             newDelta += inputAbsFunc.abs * scaleOrig;
2634          }
2635          input = absFunc(target, newDelta);
2636          return input;
2637       }
2638       if (allToppable) {
2639          input = retopFunc(target);
2640          return input;
2641       }
2642
2643       // Handle default case
2644       std::map<Absloc, std::pair<long,bool> > newFromRegs;
2645       bool anyToppedTerms = false;
2646       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
2647          Absloc fromLocOrig = (*iter).first;
2648          long scaleOrig = (*iter).second.first;
2649
2650          // Because any term with a scale != 1 is TOP, such terms do not affect
2651          // the final TOP/BOTTOM/Height value of the LEA and can be ignored.
2652          // FIXME if we change apply() to include constant propagation
2653          if (scaleOrig != 1) {
2654             anyToppedTerms = true;
2655             continue;
2656          }
2657
2658          auto findLoc = inputs.find(fromLocOrig);
2659          if (findLoc == inputs.end()) {
2660             // Easy case
2661             // Only add the term if we're not already tracking that register.
2662             // FIXME if we change apply() to include constant propagation
2663             auto found = newFromRegs.find(fromLocOrig);
2664             if (found == newFromRegs.end()) {
2665                newFromRegs.insert(make_pair(fromLocOrig,
2666                   make_pair(scaleOrig, false)));
2667             }
2668          } else {
2669             TransferFunc fromRegFunc = findLoc->second;
2670             assert(!fromRegFunc.isBottom());  // Should be special case
2671             if (fromRegFunc.isSIB()) {
2672                // Replace registers and update scales
2673                for (auto regIter = fromRegFunc.fromRegs.begin();
2674                   regIter != fromRegFunc.fromRegs.end(); ++regIter) {
2675                   Absloc replaceLoc = regIter->first;
2676                   long replaceScale = regIter->second.first;
2677                   bool replaceTopBottom = regIter->second.second;
2678                   long newScale = replaceScale * scaleOrig;
2679
2680                   // Add to our map only the registers that we aren't already
2681                   // considering.
2682                   // FIXME if we change apply() to include constant propagation
2683                   auto found = newFromRegs.find(replaceLoc);
2684                   if (found == newFromRegs.end()) {
2685                      newFromRegs.insert(make_pair(replaceLoc,
2686                         make_pair(newScale, replaceTopBottom)));
2687                   }
2688                }
2689             }
2690             if (fromRegFunc.isCopy()) {
2691                // Replace fromRegOrig with fromRegFunc.from only if we aren't
2692                // already considering fromRegFunc.from in our map.
2693                // FIXME if we change apply() to include constant propagation
2694                auto found = newFromRegs.find(fromRegFunc.from);
2695                if (found == newFromRegs.end()) {
2696                   newFromRegs.insert(make_pair(fromRegFunc.from,
2697                      make_pair(scaleOrig, fromRegFunc.isTopBottom())));
2698                }
2699             }
2700             if (fromRegFunc.isDelta()) {
2701                if (!fromRegFunc.isCopy() && !fromRegFunc.isSIB() &&
2702                   !fromRegFunc.isAbs()) {
2703                   // Add the register back in...
2704                   // FIXME if we change apply() to include constant propagation
2705                   auto found = newFromRegs.find(fromLocOrig);
2706                   if (found == newFromRegs.end()) {
2707                      newFromRegs.insert(make_pair(fromLocOrig,
2708                         make_pair(scaleOrig, fromRegFunc.isTopBottom())));
2709                   }
2710                }
2711             }
2712             if (fromRegFunc.isRetop()) {
2713                // This is a register that was re-topped due to an instruction
2714                // in this block.  Thus this term is TOP and doesn't affect the
2715                // value of the LEA, so we can ignore it.
2716                // FIXME if we change apply() to include constant propagation
2717                anyToppedTerms = true;
2718                continue;
2719             }
2720             if (fromRegFunc.isTop()) {
2721                // This is the default constructed target when the target didn't
2722                // already exist.  Keep track of this register unless we already
2723                // are.
2724                // FIXME if we change apply() to include constant propagation
2725                auto found = newFromRegs.find(fromLocOrig);
2726                if (found == newFromRegs.end()) {
2727                   newFromRegs.insert(make_pair(fromLocOrig,
2728                      make_pair(scaleOrig, false)));
2729                }
2730             }
2731          }
2732       }
2733
2734       if (anyToppedTerms) {
2735          // If any term is later discovered to be a stack height, we need to
2736          // bottom the target register since this SIB contains a topped term
2737          // (we know the topped term isn't a stack height, but we don't know
2738          // precisely what it is).  We indicate this by setting the
2739          // topBottom flag on non-topped registers.
2740          for (auto iter = newFromRegs.begin(); iter != newFromRegs.end();
2741             iter++) {
2742             iter->second.second = true;
2743          }
2744       }
2745
2746       input = sibFunc(newFromRegs, 0, target);
2747       input.topBottom = isTopBottomOrig;
2748       return input;
2749    }
2750
2751    // Copies can be tricky
2752    // apply copy logic only if registers are different
2753    if (isCopy()) {
2754       // We need to record that we want to take the inflow height
2755       // of a different register. 
2756       // Don't do an inputs[from] as that creates
2757       auto iter = inputs.find(from);
2758       if (iter == inputs.end()) {
2759          // Copying to something we haven't seen yet; easy
2760          input = *this;
2761          if (isTopBottomOrig) {
2762             input.topBottom = true;
2763             input.delta = 0;
2764          }
2765          return input;
2766       }
2767
2768       const TransferFunc &orig = iter->second;
2769
2770       if (orig.isAbs()) {
2771          // We reset the height, so we don't care about the inflow height
2772          assert(!orig.isCopy());
2773          input = orig;
2774          input.target = target;
2775          input.topBottom = false;
2776          assert(input.target.isValid());
2777
2778          if (isDelta()) {
2779             input.delta += delta;
2780          }
2781          return input;
2782       }
2783       if (orig.isCopy()) {
2784          assert(!orig.isAbs());
2785          input = orig;
2786          input.target = target;
2787          assert(input.target.isValid());
2788
2789          if (isDelta()) {
2790             input.delta += delta;
2791          }
2792          if (isTopBottomOrig || orig.isTopBottom()) {
2793             input.topBottom = true;
2794             input.delta = 0;
2795          }
2796          return input;
2797       }
2798       if (orig.isSIB()) {
2799          input = orig;
2800          input.target = target;
2801
2802          if (isDelta()) {
2803             input.delta += delta;
2804          }
2805          if (isTopBottomOrig || orig.isTopBottom()) {
2806             input.topBottom = true;
2807             input.delta = 0;
2808          }
2809          return input;
2810       }
2811
2812       // without bottom we mess up in the default case.
2813       if (orig.isBottom()) {
2814          input = bottomFunc(target);
2815          return input;
2816       }
2817
2818       if (orig.isRetop()) {
2819          input = retopFunc(target);
2820          return input;
2821       }
2822
2823       // Default case: record the copy, zero out everything else, copy over
2824       // the delta if it's defined.
2825       input.from = orig.target;
2826       input.abs = uninitialized;
2827       assert(!orig.isDelta());
2828       input.delta = 0;
2829       input.topBottom = isTopBottomOrig || orig.isTopBottom();
2830       input.fromRegs.clear();
2831    }
2832
2833    assert(!isDelta());
2834
2835    if (isRetop()) {
2836       input = *this;
2837    }
2838
2839    return input;
2840 }
2841
2842
2843 // Accumulation to the input map. This is intended to create a summary, so we
2844 // create something that can take further input.
2845 void StackAnalysis::TransferFunc::accumulate(TransferSet &inputs) {
2846    inputs[target] = summaryAccumulate(inputs);
2847 }
2848
2849
2850 void StackAnalysis::SummaryFunc::apply(const AbslocState &in,
2851    AbslocState &out) const {
2852
2853    // Copy all the elements we don't have xfer funcs for.
2854    out = in;
2855
2856    // Apply in parallel since all summary funcs are from the start of the block
2857    for (TransferSet::const_iterator iter = accumFuncs.begin();
2858       iter != accumFuncs.end(); ++iter) {
2859       assert(iter->first.isValid());
2860       out[iter->first] = iter->second.apply(in);
2861       if (out[iter->first].isTop()) {
2862          out.erase(iter->first);
2863       }
2864    }
2865 }
2866
2867
2868 void StackAnalysis::SummaryFunc::accumulate(const TransferSet &in,
2869    TransferSet &out) const {
2870
2871    // Copy all the elements we don't have xfer funcs for.
2872    out = in;
2873
2874    // Apply in parallel since all summary funcs are from the start of the block
2875    for (TransferSet::const_iterator iter = accumFuncs.begin();
2876       iter != accumFuncs.end(); ++iter) {
2877       assert(iter->first.isValid());
2878       out[iter->first] = iter->second.summaryAccumulate(in);
2879       if (out[iter->first].isTop() && !out[iter->first].isRetop()) {
2880          out.erase(iter->first);
2881       }
2882    }
2883 }
2884
2885 void StackAnalysis::SummaryFunc::add(TransferFuncs &xferFuncs) {
2886    // We need to update our register->xferFunc map
2887    // with the effects of each of the transferFuncs.
2888    for (auto iter = xferFuncs.begin(); iter != xferFuncs.end(); ++iter) {
2889       TransferFunc &func = *iter;
2890       func.accumulate(accumFuncs);
2891    }
2892    validate();
2893 }
2894
2895 void StackAnalysis::SummaryFunc::validate() const {
2896    for (TransferSet::const_iterator iter = accumFuncs.begin(); 
2897       iter != accumFuncs.end(); ++iter) {
2898       const TransferFunc &func = iter->second;
2899       assert(func.target.isValid());
2900       if (func.isCopy()) assert(!func.isAbs());
2901       if (func.isAbs()) assert(!func.isCopy());
2902       if (func.isBottom()) assert(!func.isCopy());
2903    }
2904 }
2905
2906 MachRegister StackAnalysis::sp() { 
2907    return MachRegister::getStackPointer(func->isrc()->getArch());
2908 }
2909
2910 MachRegister StackAnalysis::fp() { 
2911    return MachRegister::getFramePointer(func->isrc()->getArch());
2912 }
2913
2914 std::string StackAnalysis::format(const AbslocState &input) const {
2915    std::stringstream ret;
2916    for (AbslocState::const_iterator iter = input.begin();
2917       iter != input.end(); ++iter) {
2918       ret << iter->first.format() << " := " << iter->second.format() << ", ";
2919    }
2920    return ret.str();
2921 }
2922
2923 std::string StackAnalysis::format(const TransferSet &input) const {
2924    std::stringstream ret;
2925    for (auto iter = input.begin(); iter != input.end(); ++iter) {
2926       ret << iter->second.format() << ", ";
2927    }
2928    return ret.str();
2929 }
2930
2931
2932 // Converts a delta in a Result to a long
2933 long StackAnalysis::extractDelta(Result deltaRes) {
2934    long delta;
2935    switch(deltaRes.size()) {
2936       case 1:
2937          delta = (long)deltaRes.convert<int8_t>();
2938          break;
2939       case 2:
2940          delta = (long)deltaRes.convert<int16_t>();
2941          break;
2942       case 4:
2943          delta = (long)deltaRes.convert<int32_t>();
2944          break;
2945       case 8:
2946          delta = (long)deltaRes.convert<int64_t>();
2947          break;
2948       default:
2949          assert(0);
2950    }
2951    return delta;
2952 }
2953
2954
2955 bool StackAnalysis::getSubReg(const MachRegister &reg, MachRegister &subreg) {
2956    if (reg == x86_64::rax) subreg = x86_64::eax;
2957    else if (reg == x86_64::rbx) subreg = x86_64::ebx;
2958    else if (reg == x86_64::rcx) subreg = x86_64::ecx;
2959    else if (reg == x86_64::rdx) subreg = x86_64::edx;
2960    else if (reg == x86_64::rsp) subreg = x86_64::esp;
2961    else if (reg == x86_64::rbp) subreg = x86_64::ebp;
2962    else if (reg == x86_64::rsi) subreg = x86_64::esi;
2963    else if (reg == x86_64::rdi) subreg = x86_64::edi;
2964    else if (reg == x86_64::r8) subreg = x86_64::r8d;
2965    else if (reg == x86_64::r9) subreg = x86_64::r9d;
2966    else if (reg == x86_64::r10) subreg = x86_64::r10d;
2967    else if (reg == x86_64::r11) subreg = x86_64::r11d;
2968    else if (reg == x86_64::r12) subreg = x86_64::r12d;
2969    else if (reg == x86_64::r13) subreg = x86_64::r13d;
2970    else if (reg == x86_64::r14) subreg = x86_64::r14d;
2971    else if (reg == x86_64::r15) subreg = x86_64::r15d;
2972    else return false;
2973    return true;
2974 }
2975
2976 // If reg is an 8 byte register (rax, rbx, rcx, etc.) with a 4 byte subregister,
2977 // retops the subregister.  If reg is a 4 byte register (eax, ebx, ecx, etc.)
2978 // with an 8 byte base register, retops the base register.  The appropriate
2979 // retop transfer function is added to xferFuncs.
2980 void StackAnalysis::retopBaseSubReg(const MachRegister &reg,
2981    TransferFuncs &xferFuncs) {
2982    if (reg.size() == 4 && reg.getBaseRegister().size() == 8) {
2983       const MachRegister &baseReg = reg.getBaseRegister();
2984       xferFuncs.push_back(TransferFunc::retopFunc(Absloc(baseReg)));
2985    } else if (reg.size() == 8 && reg.getBaseRegister().size() == 8) {
2986       MachRegister subreg;
2987       if (getSubReg(reg, subreg)) {
2988          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(subreg)));
2989       }
2990    }
2991 }
2992
2993 // If reg is an 8 byte register (rax, rbx, rcx, etc.) with a 4 byte subregister,
2994 // copies the subregister into the base register.  If reg is a 4 byte register
2995 // (eax, ebx, ecx, etc.) with an 8 byte base register, copies the base register
2996 // into the subregister. The appropriate copy transfer function is added to
2997 // xferFuncs.
2998 void StackAnalysis::copyBaseSubReg(const MachRegister &reg,
2999    TransferFuncs &xferFuncs) {
3000    if (reg.size() == 4 && reg.getBaseRegister().size() == 8) {
3001       const MachRegister &baseReg = reg.getBaseRegister();
3002       xferFuncs.push_back(TransferFunc::copyFunc(Absloc(reg), Absloc(baseReg),
3003          true));
3004    } else if (reg.size() == 8 && reg.getBaseRegister().size() == 8) {
3005       MachRegister subreg;
3006       if (getSubReg(reg, subreg)) {
3007          xferFuncs.push_back(TransferFunc::copyFunc(Absloc(reg), Absloc(subreg),
3008             false));
3009       }
3010    }
3011 }
3012
3013 // If reg is an 8 byte register (rax, rbx, rcx, etc.) with a 4 byte subregister,
3014 // bottoms the subregister.  If reg is a 4 byte register (eax, ebx, ecx, etc.)
3015 // with an 8 byte base register, bottoms the base register.  The appropriate
3016 // bottom transfer function is added to xferFuncs.
3017 void StackAnalysis::bottomBaseSubReg(const MachRegister &reg,
3018    TransferFuncs &xferFuncs) {
3019    if (reg.size() == 4 && reg.getBaseRegister().size() == 8) {
3020       const MachRegister &baseReg = reg.getBaseRegister();
3021       xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(baseReg)));
3022    } else if (reg.size() == 8 && reg.getBaseRegister().size() == 8) {
3023       MachRegister subreg;
3024       if (getSubReg(reg, subreg)) {
3025          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(subreg)));
3026       }
3027    }
3028 }