Improve handling of XOR.
[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       return;
828    }
829
830
831    if (insn->writesMemory()) {
832       // xor mem1, reg2/imm2
833       assert(writtenSet.size() == 0);
834
835       // Extract the expression inside the dereference
836       std::vector<Expression::Ptr> &addrExpr = children0;
837       assert(addrExpr.size() == 1);
838
839       // Try to determine the written memory address
840       Absloc writtenLoc;
841       StateEvalVisitor visitor;
842       if (intervals_ == NULL) {
843          visitor = StateEvalVisitor(off, insn, NULL);
844       } else {
845          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
846       }
847       addrExpr[0]->apply(&visitor);
848       if (visitor.isDefined()) {
849          std::pair<Address, bool> resultPair = visitor.getResult();
850          if (resultPair.second) {
851             // We have a stack slot
852             writtenLoc = Absloc(resultPair.first, 0, NULL);
853          } else {
854             // We have a static address
855             writtenLoc = Absloc(resultPair.first);
856          }
857       } else {
858          // Couldn't determine written location, so assume it's not on the stack
859          // and ignore it.
860          return;
861       }
862
863       if (readSet.size() > 0) {
864          // xor mem1, reg2
865          assert(readSet.size() == 1);
866          Absloc from((*readSet.begin())->getID());
867          std::map<Absloc, std::pair<long, bool>> fromRegs;
868          fromRegs[writtenLoc] = std::make_pair(1, true);
869          fromRegs[from] = std::make_pair(1, true);
870          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, 0, writtenLoc));
871       } else {
872          // xor mem1, imm2
873          // Xor with immediate.  Set topBottom on target loc
874          Expression::Ptr immExpr = operands[1].getValue();
875          assert(typeid(*immExpr) == typeid(Immediate));
876          xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc,
877             true));
878       }
879       return;
880    }
881
882
883    assert(writtenSet.size() == 1);
884    MachRegister written = (*writtenSet.begin())->getID();
885    Absloc writtenLoc(written);
886
887    if (insn->readsMemory()) {
888       // xor reg1, mem2
889       // Extract the expression inside the dereference
890       std::vector<Expression::Ptr> &addrExpr = children1;
891       assert(addrExpr.size() == 1);
892
893       // Try to determine the read memory address
894       StateEvalVisitor visitor;
895       if (intervals_ == NULL) {
896          visitor = StateEvalVisitor(off, insn, NULL);
897       } else {
898          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
899       }
900       addrExpr[0]->apply(&visitor);
901       if (visitor.isDefined()) {
902          std::pair<Address, bool> resultPair = visitor.getResult();
903          Absloc readLoc;
904          if (resultPair.second) {
905             // We have a stack slot
906             readLoc = Absloc(resultPair.first, 0, NULL);
907          } else {
908             // We have a static address
909             readLoc = Absloc(resultPair.first);
910          }
911          std::map<Absloc, std::pair<long, bool>> fromRegs;
912          fromRegs[writtenLoc] = std::make_pair(1, true);
913          fromRegs[readLoc] = std::make_pair(1, true);
914          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, 0, writtenLoc));
915       } else {
916          // Couldn't determine the read location.  Assume it's not on the stack.
917          xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc,
918             true));
919       }
920       return;
921    }
922
923
924    // xor reg1, reg2/imm2
925    MachRegister read;
926    if (!readSet.empty()) {
927       assert(readSet.size() == 1);
928       read = (*readSet.begin())->getID();
929    }
930    Absloc readLoc(read);
931
932    if (read.isValid()) {
933       // xor reg1, reg2
934       std::map<Absloc, std::pair<long, bool>> fromRegs;
935       fromRegs[writtenLoc] = std::make_pair(1, true);
936       fromRegs[readLoc] = std::make_pair(1, true);
937       xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, 0, writtenLoc));
938    } else {
939       // xor reg1, imm1
940       InstructionAPI::Expression::Ptr readExpr = operands[1].getValue();
941       assert(typeid(*readExpr) == typeid(InstructionAPI::Immediate));
942       xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc, true));
943    }
944 }
945
946
947 void StackAnalysis::handleDiv(Instruction::Ptr insn,
948    TransferFuncs &xferFuncs) {
949    stackanalysis_printf("\t\t\thandleDiv: %s\n", insn->format().c_str());
950    std::vector<Operand> operands;
951    insn->getOperands(operands);
952    assert(operands.size() == 3);
953
954    Expression::Ptr quotient = operands[1].getValue();
955    Expression::Ptr remainder = operands[0].getValue();
956    Expression::Ptr divisor = operands[2].getValue();
957    assert(typeid(*quotient) == typeid(RegisterAST));
958    assert(typeid(*remainder) == typeid(RegisterAST));
959    assert(typeid(*divisor) != typeid(Immediate));
960
961    MachRegister quotientReg = (boost::dynamic_pointer_cast<InstructionAPI::
962       RegisterAST>(quotient))->getID();
963    MachRegister remainderReg = (boost::dynamic_pointer_cast<InstructionAPI::
964       RegisterAST>(remainder))->getID();
965
966    xferFuncs.push_back(TransferFunc::retopFunc(Absloc(quotientReg)));
967    xferFuncs.push_back(TransferFunc::retopFunc(Absloc(remainderReg)));
968 }
969
970
971 void StackAnalysis::handleMul(Instruction::Ptr insn,
972    TransferFuncs &xferFuncs) {
973    // MULs have a few forms:
974    //   1. mul reg1, reg2/mem2
975    //     -- reg1 = reg1 * reg2/mem2
976    //   2. mul reg1, reg2/mem2, imm3
977    //     -- reg1 = reg2/mem2 * imm3
978    //   3. mul reg1, reg2, reg3/mem3
979    //     -- reg1:reg2 = reg2 * reg3/mem3
980    stackanalysis_printf("\t\t\thandleMul: %s\n", insn->format().c_str());
981    std::vector<Operand> operands;
982    insn->getOperands(operands);
983    assert(operands.size() == 2 || operands.size() == 3);
984
985    Expression::Ptr target = operands[0].getValue();
986    assert(typeid(*target) == typeid(RegisterAST));
987    MachRegister targetReg = (boost::dynamic_pointer_cast<InstructionAPI::
988       RegisterAST>(target))->getID();
989
990    if (operands.size() == 2) {
991       // Form 1
992       xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
993    } else {
994       Expression::Ptr multiplicand = operands[1].getValue();
995       Expression::Ptr multiplier = operands[2].getValue();
996
997       if (typeid(*multiplier) == typeid(Immediate)) {
998          // Form 2
999          assert(typeid(*multiplicand) == typeid(RegisterAST) ||
1000             typeid(*multiplicand) == typeid(Dereference));
1001          long multiplierVal = multiplier->eval().convert<long>();
1002          if (multiplierVal == 0) {
1003             xferFuncs.push_back(TransferFunc::absFunc(Absloc(targetReg), 0));
1004          } else if (multiplierVal == 1) {
1005             if (typeid(*multiplicand) == typeid(RegisterAST)) {
1006                // mul reg1, reg2, 1
1007                MachRegister multiplicandReg = boost::dynamic_pointer_cast<
1008                   RegisterAST>(multiplicand)->getID();
1009                Absloc targetLoc(targetReg);
1010                Absloc multiplicandLoc(multiplicandReg);
1011                xferFuncs.push_back(TransferFunc::copyFunc(multiplicandLoc,
1012                   targetLoc));
1013             } else {
1014                // mul reg1, mem2, 1
1015                Absloc targetLoc(targetReg);
1016                xferFuncs.push_back(TransferFunc::bottomFunc(targetLoc));
1017             }
1018          } else {
1019             xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
1020          }
1021       } else {
1022          // Form 3
1023          assert(typeid(*multiplicand) == typeid(RegisterAST));
1024          assert(typeid(*multiplier) == typeid(RegisterAST) ||
1025             typeid(*multiplier) == typeid(Dereference));
1026          MachRegister multiplicandReg = boost::dynamic_pointer_cast<
1027             RegisterAST>(multiplicand)->getID();
1028          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(targetReg)));
1029          xferFuncs.push_back(TransferFunc::retopFunc(Absloc(multiplicandReg)));
1030       }
1031    }
1032 }
1033
1034
1035 void StackAnalysis::handlePushPop(Instruction::Ptr insn, Block *block,
1036    const Offset off, int sign, TransferFuncs &xferFuncs) {
1037
1038    long delta = 0;
1039    Operand arg = insn->getOperand(0);
1040    // Why was this here? bernat, 12JAN11
1041    if (arg.getValue()->eval().defined) {
1042       delta = sign * word_size;
1043       stackanalysis_printf(
1044          "\t\t\t Stack height changed by evaluated push/pop: %lx\n", delta);
1045    }
1046    else {
1047       delta = sign * arg.getValue()->size();
1048       //cerr << "Odd case: set delta to " << hex << delta << dec <<
1049       //   " for instruction " << insn->format() << endl;
1050       stackanalysis_printf(
1051          "\t\t\t Stack height changed by unevalled push/pop: %lx\n", delta);
1052    }
1053    //   delta = sign *arg.getValue()->size();
1054    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
1055
1056
1057    if (insn->getOperation().getID() == e_push && insn->writesMemory()) {
1058       // This is a push.  Let's record the value pushed on the stack if
1059       // possible.
1060       if (intervals_ != NULL) {
1061          Absloc sploc(sp());
1062          Height spHeight = (*intervals_)[block][off][sploc];
1063          if (!spHeight.isTop() && !spHeight.isBottom()) {
1064             // Get written stack slot
1065             long writtenSlotHeight = spHeight.height() - word_size;
1066             Absloc writtenLoc(writtenSlotHeight, 0, NULL);
1067
1068             // Get copied register
1069             Expression::Ptr readExpr = insn->getOperand(0).getValue();
1070             assert(typeid(*readExpr) == typeid(RegisterAST));
1071             MachRegister readReg = boost::dynamic_pointer_cast<RegisterAST>(
1072                readExpr)->getID();
1073             Absloc readLoc(readReg);
1074
1075             xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1076          }
1077       }
1078    } else if (insn->getOperation().getID() == e_pop && !insn->writesMemory()) {
1079       // This is a pop.  Let's record the value popped if possible.
1080
1081       // Get target register
1082       Expression::Ptr targExpr = insn->getOperand(0).getValue();
1083       assert(typeid(*targExpr) == typeid(RegisterAST));
1084       MachRegister targReg = boost::dynamic_pointer_cast<RegisterAST>(
1085          targExpr)->getID();
1086       Absloc targLoc(targReg);
1087
1088       if (intervals_ != NULL) {
1089          Absloc sploc(sp());
1090          Height spHeight = (*intervals_)[block][off][sploc];
1091          if (spHeight.isTop()) {
1092             // Load from a topped location. Since StackMod fails when storing
1093             // to an undetermined topped location, it is safe to assume the
1094             // value loaded here is not a stack height.
1095             xferFuncs.push_back(TransferFunc::retopFunc(targLoc));
1096          } else if (spHeight.isBottom()) {
1097             xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1098          } else {
1099             // Get copied stack slot
1100             long readSlotHeight = spHeight.height();
1101             Absloc readLoc(readSlotHeight, 0, NULL);
1102
1103             xferFuncs.push_back(TransferFunc::copyFunc(readLoc, targLoc));
1104          }
1105       } else {
1106          xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1107       }
1108    } else {
1109       assert(false);
1110    }
1111 }
1112
1113 void StackAnalysis::handleReturn(Instruction::Ptr insn,
1114    TransferFuncs &xferFuncs) {
1115    long delta = 0;
1116    std::vector<Operand> operands;
1117    insn->getOperands(operands);
1118    if (operands.size() < 2) {
1119       delta = word_size;
1120    } else {
1121       fprintf(stderr, "Unhandled RET instruction: %s\n",
1122          insn->format().c_str());
1123       assert(false);
1124    }
1125 /*   else if (operands.size() == 1) {
1126       // Ret immediate
1127       Result imm = operands[0].getValue()->eval();
1128       if (imm.defined) {
1129          delta = word_size + imm.convert<int>();
1130       }
1131       else {
1132          stackanalysis_printf("\t\t\t Stack height changed by return: bottom\n");
1133          xferFuncs.push_back(TransferFunc::bottomFunc(Absloc(sp())));
1134       }
1135    }
1136 */
1137    stackanalysis_printf("\t\t\t Stack height changed by return: %lx\n", delta);
1138    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), delta));
1139 }
1140
1141
1142 void StackAnalysis::handleAddSub(Instruction::Ptr insn, Block *block,
1143    const Offset off, int sign, TransferFuncs &xferFuncs) {
1144    // Possible forms for add/sub:
1145    //   1. add reg1, reg2
1146    //     -- reg1 = reg1 + reg2
1147    //   2. add reg1, mem2
1148    //     -- reg1 = reg1 + mem2
1149    //   3. add mem1, reg2
1150    //     -- mem1 = mem1 + reg2
1151    //   4. add reg1, imm2
1152    //     -- reg1 = reg1 + imm2
1153    //   5. add mem1, imm2
1154    //     -- mem1 = mem1 + imm2
1155    //
1156    //   #1 is handled by setting reg1 to a sibFunc of reg1 and reg2.
1157    //   #2 depends on whether or not the location of mem2 can be determined
1158    //      statically.
1159    //      a. If it can, reg1 is set to a sibFunc of reg1 and mem2.
1160    //      b. Otherwise, reg1 is set to topBottom.
1161    //   #3 depends on whether or not the location of mem1 can be determined
1162    //      statically.
1163    //      a. If it can, mem1 is set to a sibFunc of mem1 and reg2.
1164    //      b. Otherwise, nothing happens.
1165    //   #4 is handled with a delta.
1166    //   #5 depends on whether or not the location of mem1 can be determined
1167    //      statically.
1168    //      a. If it can, mem1 is handled with a delta.
1169    //      b. Otherwise, nothing happens.
1170
1171    stackanalysis_printf("\t\t\t handleAddSub, insn = %s\n",
1172       insn->format().c_str());
1173    Architecture arch = insn->getArch();  // Needed for debug messages
1174    std::vector<Operand> operands;
1175    insn->getOperands(operands);
1176    assert(operands.size() == 2);
1177
1178    std::set<RegisterAST::Ptr> readSet;
1179    std::set<RegisterAST::Ptr> writeSet;
1180    operands[1].getReadSet(readSet);
1181    operands[0].getWriteSet(writeSet);
1182
1183    if (insn->writesMemory()) {
1184       // Cases 3 and 5
1185       assert(writeSet.size() == 0);
1186       stackanalysis_printf("\t\t\tMemory add/sub to: %s\n",
1187          operands[0].format(arch).c_str());
1188
1189       // Extract the expression inside the dereference
1190       std::vector<Expression::Ptr> addrExpr;
1191       operands[0].getValue()->getChildren(addrExpr);
1192       assert(addrExpr.size() == 1);
1193
1194       // Try to determine the written memory address
1195       Absloc writtenLoc;
1196       StateEvalVisitor visitor;
1197       if (intervals_ == NULL) {
1198          visitor = StateEvalVisitor(off, insn, NULL);
1199       } else {
1200          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1201       }
1202       addrExpr[0]->apply(&visitor);
1203       if (visitor.isDefined()) {
1204          std::pair<Address, bool> resultPair = visitor.getResult();
1205          if (resultPair.second) {
1206             // We have a stack slot
1207             writtenLoc = Absloc(resultPair.first, 0, NULL);
1208          } else {
1209             // We have a static address
1210             writtenLoc = Absloc(resultPair.first);
1211          }
1212          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1213             writtenLoc.format().c_str());
1214       } else {
1215          // Cases 3b and 5b
1216          stackanalysis_printf("\t\t\tCan't determine location\n");
1217          return;
1218       }
1219
1220       if (readSet.size() > 0) {
1221          // Case 3a
1222          assert(readSet.size() == 1);
1223          std::map<Absloc, std::pair<long, bool>> terms;
1224          Absloc src((*readSet.begin())->getID());
1225          Absloc &dest = writtenLoc;
1226          terms[src] = make_pair(sign, false);
1227          terms[dest] = make_pair(1, false);
1228          xferFuncs.push_back(TransferFunc::sibFunc(terms, 0, dest));
1229       } else {
1230          // Case 5a
1231          Expression::Ptr immExpr = operands[1].getValue();
1232          assert(typeid(*immExpr) == typeid(Immediate));
1233          long immVal = immExpr->eval().convert<long>();
1234          xferFuncs.push_back(TransferFunc::deltaFunc(writtenLoc,
1235             sign * immVal));
1236       }
1237       return;
1238    }
1239
1240    // Cases 1, 2, and 4
1241    assert(writeSet.size() == 1);
1242    MachRegister written = (*writeSet.begin())->getID();
1243    Absloc writtenLoc(written);
1244
1245    if (insn->readsMemory()) {
1246       // Case 2
1247       stackanalysis_printf("\t\t\tAdd/sub from: %s\n",
1248          operands[1].format(arch).c_str());
1249
1250       // Extract the expression inside the dereference
1251       std::vector<Expression::Ptr> addrExpr;
1252       operands[1].getValue()->getChildren(addrExpr);
1253       assert(addrExpr.size() == 1);
1254
1255       // Try to determine the read memory address
1256       StateEvalVisitor visitor;
1257       if (intervals_ == NULL) {
1258          visitor = StateEvalVisitor(off, insn, NULL);
1259       } else {
1260          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1261       }
1262       addrExpr[0]->apply(&visitor);
1263       if (visitor.isDefined()) {
1264          // Case 2a
1265          std::pair<Address, bool> resultPair = visitor.getResult();
1266          Absloc readLoc;
1267          if (resultPair.second) {
1268             // We have a stack slot
1269             readLoc = Absloc(resultPair.first, 0, NULL);
1270          } else {
1271             // We have a static address
1272             readLoc = Absloc(resultPair.first);
1273          }
1274          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1275             readLoc.format().c_str());
1276          std::map<Absloc, std::pair<long, bool>> terms;
1277          terms[readLoc] = make_pair(sign, false);
1278          terms[writtenLoc] = make_pair(1, false);
1279          xferFuncs.push_back(TransferFunc::sibFunc(terms, 0, writtenLoc));
1280       } else {
1281          // Case 2b
1282          stackanalysis_printf("\t\t\tCan't determine location\n");
1283          xferFuncs.push_back(TransferFunc::copyFunc(writtenLoc, writtenLoc,
1284             true));
1285       }
1286       return;
1287    }
1288
1289    Result res = operands[1].getValue()->eval();
1290    if (res.defined) {
1291       // Case 4
1292       long delta = sign * extractDelta(res);
1293       stackanalysis_printf("\t\t\t Register changed by add/sub: %lx\n", delta);
1294       xferFuncs.push_back(TransferFunc::deltaFunc(writtenLoc, delta));
1295    } else {
1296       // Case 1
1297       std::map<Absloc, std::pair<long, bool>> terms;
1298       Absloc src((*readSet.begin())->getID());
1299       Absloc &dest = writtenLoc;
1300       terms[src] = make_pair(sign, false);
1301       terms[dest] = make_pair(1, false);
1302       xferFuncs.push_back(TransferFunc::sibFunc(terms, 0, dest));
1303    }
1304 }
1305
1306 void StackAnalysis::handleLEA(Instruction::Ptr insn,
1307    TransferFuncs &xferFuncs) {
1308    // LEA has a few patterns:
1309    //   op0: target register
1310    //-------------------------------
1311    //   op1: reg + reg * imm + imm
1312    //            or
1313    //   op1: reg + reg * imm
1314    //            or
1315    //   op1: imm + reg * imm
1316    //            or
1317    //   op1: reg + imm
1318    //            or
1319    //   op1: reg
1320    //
1321
1322    stackanalysis_printf("\t\t\t handleLEA, insn = %s\n",
1323       insn->format().c_str());
1324
1325    std::set<RegisterAST::Ptr> readSet;
1326    std::set<RegisterAST::Ptr> writtenSet;
1327    insn->getOperand(0).getWriteSet(writtenSet);
1328    insn->getOperand(1).getReadSet(readSet);
1329    assert(writtenSet.size() == 1);
1330    assert(readSet.size() == 1 || readSet.size() == 2);
1331    MachRegister written = (*writtenSet.begin())->getID();
1332    Absloc writeloc(written);
1333
1334    InstructionAPI::Operand srcOperand = insn->getOperand(1);
1335    InstructionAPI::Expression::Ptr srcExpr = srcOperand.getValue();
1336    std::vector<InstructionAPI::Expression::Ptr> children;
1337    srcExpr->getChildren(children);
1338
1339    stackanalysis_printf("\t\t\t\t srcOperand = %s\n",
1340       srcExpr->format().c_str());
1341
1342    if (readSet.size() == 1) {
1343       InstructionAPI::Expression::Ptr regExpr, scaleExpr, deltaExpr;
1344       bool foundScale = false;
1345       bool foundDelta = false;
1346
1347       if (children.size() == 2) {
1348          if (typeid(*children[0]) == typeid(Immediate)) {
1349             // op1: imm + reg * imm
1350             deltaExpr = children[0];
1351             Expression::Ptr scaleIndexExpr = children[1];
1352             assert(typeid(*scaleIndexExpr) == typeid(BinaryFunction));
1353             children.clear();
1354             scaleIndexExpr->getChildren(children);
1355
1356             regExpr = children[0];
1357             scaleExpr = children[1];
1358             assert(typeid(*regExpr) == typeid(RegisterAST));
1359             assert(typeid(*scaleExpr) == typeid(Immediate));
1360             foundScale = true;
1361             foundDelta = true;
1362          } else if (typeid(*children[0]) == typeid(RegisterAST)) {
1363             // op1: reg + imm
1364             regExpr = children[0];
1365             deltaExpr = children[1];
1366             stackanalysis_printf("\t\t\t\t reg: %s\n",
1367                regExpr->format().c_str());
1368             stackanalysis_printf("\t\t\t\t delta: %s\n",
1369                deltaExpr->format().c_str());
1370             assert(typeid(*regExpr) == typeid(RegisterAST));
1371             assert(typeid(*deltaExpr) == typeid(Immediate));
1372             foundDelta = true;
1373          } else {
1374             assert(false);
1375          }
1376       } else if (children.size() == 0) {
1377          // op1: reg
1378          regExpr = srcExpr;
1379          assert(typeid(*regExpr) == typeid(RegisterAST));
1380       } else {
1381          assert(false);
1382       }
1383
1384       MachRegister reg = (boost::dynamic_pointer_cast<InstructionAPI::
1385          RegisterAST>(regExpr))->getID();
1386
1387       long scale = 1;
1388       if (foundScale) {
1389          scale = scaleExpr->eval().convert<long>();
1390       }
1391
1392       long delta = 0;
1393       if (foundDelta) {
1394          delta = extractDelta(deltaExpr->eval());
1395       }
1396
1397       if (foundScale) {
1398          std::map<Absloc,std::pair<long, bool> > fromRegs;
1399          fromRegs.insert(make_pair(Absloc(reg), make_pair(scale, false)));
1400          xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, delta, writeloc));
1401       } else {
1402          Absloc readloc(reg);
1403          TransferFunc lea = TransferFunc::copyFunc(readloc, writeloc);
1404          lea.delta = delta;
1405          xferFuncs.push_back(lea);
1406       }
1407    } else if (readSet.size() == 2) {
1408       Expression::Ptr baseExpr, indexExpr, scaleExpr, deltaExpr;
1409       bool foundDelta = false;
1410
1411       assert(children.size() == 2);
1412       if (typeid(*children[1]) == typeid(Immediate)) {
1413          // op1: reg + reg * imm + imm
1414          // Extract the delta and continue on to get base, index, and scale
1415          deltaExpr = children[1];
1416          stackanalysis_printf("\t\t\t\t delta: %s\n",
1417             deltaExpr->format().c_str());
1418          Expression::Ptr sibExpr = children[0];
1419          assert(typeid(*sibExpr) == typeid(BinaryFunction));
1420          children.clear();
1421          sibExpr->getChildren(children);
1422          assert(children.size() == 2);
1423          foundDelta = true;
1424       }
1425
1426       // op1: reg + reg * imm
1427       baseExpr = children[0];
1428       Expression::Ptr scaleIndexExpr = children[1];
1429       stackanalysis_printf("\t\t\t\t base: %s\n", baseExpr->format().c_str());
1430       assert(typeid(*scaleIndexExpr) == typeid(BinaryFunction));
1431
1432       // Extract the index and scale
1433       children.clear();
1434       scaleIndexExpr->getChildren(children);
1435       assert(children.size() == 2);
1436       indexExpr = children[0];
1437       scaleExpr = children[1];
1438       stackanalysis_printf("\t\t\t\t index: %s\n",
1439          indexExpr->format().c_str());
1440       stackanalysis_printf("\t\t\t\t scale: %s\n",
1441          scaleExpr->format().c_str());
1442
1443       assert(typeid(*baseExpr) == typeid(RegisterAST));
1444       assert(typeid(*indexExpr) == typeid(RegisterAST));
1445       assert(typeid(*scaleExpr) == typeid(Immediate));
1446
1447       MachRegister base = (boost::dynamic_pointer_cast<InstructionAPI::
1448          RegisterAST>(baseExpr))->getID();
1449       MachRegister index = (boost::dynamic_pointer_cast<InstructionAPI::
1450          RegisterAST>(indexExpr))->getID();
1451       long scale = scaleExpr->eval().convert<long>();
1452
1453       long delta = 0;
1454       if (foundDelta) {
1455          Result deltaRes = deltaExpr->eval();
1456          delta = extractDelta(deltaRes);
1457       }
1458
1459       assert(base.isValid() && index.isValid() && scale != -1);
1460
1461       // Consolidate when possible
1462       if (base == index) {
1463          base = MachRegister();
1464          scale++;
1465       }
1466
1467       std::map<Absloc,std::pair<long,bool> > fromRegs;
1468       if (base.isValid()) {
1469          fromRegs.insert(make_pair(Absloc(base), make_pair(1, false)));
1470       }
1471       fromRegs.insert(make_pair(Absloc(index), make_pair(scale, false)));
1472       xferFuncs.push_back(TransferFunc::sibFunc(fromRegs, delta, writeloc));
1473    } else {
1474       assert(false);
1475    }
1476 }
1477
1478 void StackAnalysis::handleLeave(Block *block, const Offset off,
1479    TransferFuncs &xferFuncs) {
1480    // This is... mov esp, ebp; pop ebp.
1481    // Handle it as such.
1482
1483    // mov esp, ebp;
1484    xferFuncs.push_back(TransferFunc::copyFunc(Absloc(fp()), Absloc(sp())));
1485
1486    // pop ebp: adjust stack pointer
1487    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), word_size));
1488
1489    // pop ebp: copy value from stack to ebp
1490    Absloc targLoc(fp());
1491    if (intervals_ != NULL) {
1492       Absloc sploc(sp());
1493       Height spHeight = (*intervals_)[block][off][sploc];
1494       if (spHeight.isTop()) {
1495          // Load from a topped location. Since StackMod fails when storing
1496          // to an undetermined topped location, it is safe to assume the
1497          // value loaded here is not a stack height.
1498          xferFuncs.push_back(TransferFunc::retopFunc(targLoc));
1499       } else if (spHeight.isBottom()) {
1500          xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1501       } else {
1502          // Get copied stack slot
1503          long readSlotHeight = spHeight.height();
1504          Absloc readLoc(readSlotHeight, 0, NULL);
1505
1506          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, targLoc));
1507       }
1508    } else {
1509       xferFuncs.push_back(TransferFunc::bottomFunc(targLoc));
1510    }
1511 }
1512
1513 void StackAnalysis::handlePushPopFlags(int sign, TransferFuncs &xferFuncs) {
1514    // Fixed-size push/pop
1515    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()), sign * word_size));
1516 }
1517
1518 void StackAnalysis::handlePushPopRegs(int sign, TransferFuncs &xferFuncs) {
1519    // Fixed-size push/pop
1520    // 8 registers
1521    xferFuncs.push_back(TransferFunc::deltaFunc(Absloc(sp()),
1522       sign * 8 * word_size));
1523 }
1524
1525 void StackAnalysis::handlePowerAddSub(Instruction::Ptr insn, int sign,
1526    TransferFuncs &xferFuncs) {
1527
1528    // Add/subtract are op0 = op1 +/- op2; we'd better read the stack pointer as
1529    // well as writing it
1530    if (!insn->isRead(theStackPtr) ||
1531       !insn->isWritten(theStackPtr)) {
1532       return handleDefault(insn, xferFuncs);
1533    }
1534    
1535    Operand arg = insn->getOperand(2);
1536    Result res = arg.getValue()->eval();
1537    Absloc sploc(sp());
1538    if (res.defined) {
1539       xferFuncs.push_back(TransferFunc::deltaFunc(sploc,
1540          sign * res.convert<long>()));
1541       stackanalysis_printf(
1542          "\t\t\t Stack height changed by evalled add/sub: %lx\n",
1543          sign * res.convert<long>());
1544    } else {
1545       xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1546       stackanalysis_printf(
1547          "\t\t\t Stack height changed by unevalled add/sub: bottom\n");
1548    }
1549 }
1550
1551 void StackAnalysis::handlePowerStoreUpdate(Instruction::Ptr insn,
1552    TransferFuncs &xferFuncs) {
1553
1554    if (!insn->isWritten(theStackPtr)) {
1555       return handleDefault(insn, xferFuncs);
1556    }
1557    
1558    std::set<Expression::Ptr> memWriteAddrs;
1559    insn->getMemoryWriteOperands(memWriteAddrs);
1560    Expression::Ptr stackWrite = *(memWriteAddrs.begin());
1561    stackanalysis_printf("\t\t\t ...checking operand %s\n",
1562       stackWrite->format().c_str());
1563    stackanalysis_printf("\t\t\t ...binding %s to 0\n",
1564       theStackPtr->format().c_str());
1565    stackWrite->bind(theStackPtr.get(), Result(u32, 0));
1566    Result res = stackWrite->eval();
1567    Absloc sploc(sp());
1568    if (res.defined) {
1569       long delta = res.convert<long>();
1570       xferFuncs.push_back(TransferFunc::deltaFunc(sploc, delta));
1571       stackanalysis_printf(
1572          "\t\t\t Stack height changed by evalled stwu: %lx\n", delta);
1573    }
1574    else {
1575       xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
1576       stackanalysis_printf(
1577          "\t\t\t Stack height changed by unevalled stwu: bottom\n");
1578    }
1579 }
1580
1581
1582 void StackAnalysis::handleMov(Instruction::Ptr insn, Block *block,
1583    const Offset off, TransferFuncs &xferFuncs) {
1584    // Some cases:
1585    //   1. mov reg, reg
1586    //   2. mov imm, reg
1587    //   3. mov mem, reg
1588    //   4. mov reg, mem
1589    //   5. mov imm, mem
1590    // 
1591    // #1 Causes register copying.
1592    // #2 Causes an absolute value in the register.
1593    // #3 Depends on whether the memory address we're loading from can be
1594    //    determined statically.
1595    //    a. If it can, we copy the register to the memory location we're
1596    //       loading from.
1597    //    b. Otherwise, we set the register to TOP.  Note that this is safe
1598    //       since StackMod fails whenever a stack height is written out to an
1599    //       undetermined (topped) location.
1600    // #4 Depends on whether the address we're storing to can be determined
1601    //    statically.
1602    //    a. If it can, we copy the memory address to the register.
1603    //    b. Otherwise, we ignore the store.
1604    // #5 Depends on whether the address we're storing to can be determined
1605    //    statically.
1606    //    a. If it can, we give the address an absolute value.
1607    //    b. Otherwise, we ignore the store.
1608
1609    Architecture arch = insn->getArch();  // Needed for debug messages
1610
1611    // Extract operands
1612    std::vector<Operand> operands;
1613    insn->getOperands(operands);
1614    assert(operands.size() == 2);
1615
1616    // Extract written/read register sets
1617    std::set<RegisterAST::Ptr> writtenRegs;
1618    std::set<RegisterAST::Ptr> readRegs;
1619    operands[0].getWriteSet(writtenRegs);
1620    operands[1].getReadSet(readRegs);
1621
1622
1623    if (insn->writesMemory()) {
1624       assert(writtenRegs.size() == 0);
1625       stackanalysis_printf("\t\t\tMemory write to: %s\n",
1626          operands[0].format(arch).c_str());
1627
1628       // Extract the expression inside the dereference
1629       std::vector<Expression::Ptr> addrExpr;
1630       operands[0].getValue()->getChildren(addrExpr);
1631       assert(addrExpr.size() == 1);
1632
1633       // Try to determine the written memory address
1634       Absloc writtenLoc;
1635       StateEvalVisitor visitor;
1636       if (intervals_ == NULL) {
1637          visitor = StateEvalVisitor(off, insn, NULL);
1638       } else {
1639          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1640       }
1641       addrExpr[0]->apply(&visitor);
1642       if (visitor.isDefined()) {
1643          std::pair<Address, bool> resultPair = visitor.getResult();
1644          if (resultPair.second) {
1645             // We have a stack slot
1646             writtenLoc = Absloc(resultPair.first, 0, NULL);
1647          } else {
1648             // We have a static address
1649             writtenLoc = Absloc(resultPair.first);
1650          }
1651          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1652             writtenLoc.format().c_str());
1653       } else {
1654          // Cases 4b and 5b
1655          stackanalysis_printf("\t\t\tCan't determine location\n");
1656          return;
1657       }
1658
1659       if (readRegs.size() > 0) {
1660          // Case 4a
1661          assert(readRegs.size() == 1);
1662          Absloc from((*readRegs.begin())->getID());
1663          xferFuncs.push_back(TransferFunc::copyFunc(from, writtenLoc));
1664       } else {
1665          // Case 5a
1666          Expression::Ptr immExpr = operands[1].getValue();
1667          assert(typeid(*immExpr) == typeid(Immediate));
1668          long immVal = immExpr->eval().convert<long>();
1669          xferFuncs.push_back(TransferFunc::absFunc(writtenLoc, immVal));
1670       }
1671       return;
1672    }
1673
1674
1675    // Only Cases 1, 2, and 3 can reach this point.
1676    // As a result, we know there's exactly one written register.
1677    assert(writtenRegs.size() == 1);
1678    MachRegister written = (*writtenRegs.begin())->getID();
1679    Absloc writtenLoc(written);
1680
1681    if (insn->readsMemory()) {
1682       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1683          operands[1].format(arch).c_str());
1684
1685       // Extract the expression inside the dereference
1686       std::vector<Expression::Ptr> addrExpr;
1687       operands[1].getValue()->getChildren(addrExpr);
1688       assert(addrExpr.size() == 1);
1689
1690       // Try to determine the read memory address
1691       StateEvalVisitor visitor;
1692       if (intervals_ == NULL) {
1693          visitor = StateEvalVisitor(off, insn, NULL);
1694       } else {
1695          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1696       }
1697       addrExpr[0]->apply(&visitor);
1698       if (visitor.isDefined()) {
1699          // Case 3a
1700          std::pair<Address, bool> resultPair = visitor.getResult();
1701          Absloc readLoc;
1702          if (resultPair.second) {
1703             // We have a stack slot
1704             readLoc = Absloc(resultPair.first, 0, NULL);
1705          } else {
1706             // We have a static address
1707             readLoc = Absloc(resultPair.first);
1708          }
1709          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1710             readLoc.format().c_str());
1711          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1712       } else {
1713          // Case 3b
1714          stackanalysis_printf("\t\t\tCan't determine location\n");
1715          xferFuncs.push_back(TransferFunc::retopFunc(writtenLoc));
1716       }
1717       return;
1718    }
1719
1720
1721    // Only Cases 1 and 2 can reach this point.
1722    // As a result, we know there's either 0 or 1 read registers
1723    MachRegister read;
1724    if (!readRegs.empty()) {
1725       assert(readRegs.size() == 1);
1726       read = (*readRegs.begin())->getID();
1727    }
1728    Absloc readLoc(read);
1729
1730
1731    if (read.isValid()) {
1732       // Case 1
1733       stackanalysis_printf("\t\t\tCopy detected: %s -> %s\n",
1734          read.name().c_str(), written.name().c_str());
1735       xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1736    } else {
1737       // Case 2
1738       InstructionAPI::Expression::Ptr readExpr = operands[1].getValue();
1739       assert(typeid(*readExpr) == typeid(InstructionAPI::Immediate));
1740       long readValue = readExpr->eval().convert<long>();
1741       stackanalysis_printf("\t\t\tImmediate to register move: %s set to %ld\n",
1742          written.name().c_str(), readValue);
1743       xferFuncs.push_back(TransferFunc::absFunc(writtenLoc, readValue));
1744       return;
1745    }
1746 }
1747
1748 void StackAnalysis::handleZeroExtend(Instruction::Ptr insn, Block *block,
1749    const Offset off, TransferFuncs &xferFuncs) {
1750    // In x86/x86_64, zero extends can't write to memory
1751    assert(!insn->writesMemory());
1752
1753    Architecture arch = insn->getArch();  // Needed for debug messages
1754
1755    // Extract operands
1756    std::vector<Operand> operands;
1757    insn->getOperands(operands);
1758    assert(operands.size() == 2);
1759
1760    // Extract written/read register sets
1761    std::set<RegisterAST::Ptr> writtenRegs;
1762    std::set<RegisterAST::Ptr> readRegs;
1763    operands[0].getWriteSet(writtenRegs);
1764    operands[1].getReadSet(readRegs);
1765
1766    assert(writtenRegs.size() == 1);
1767    Absloc writtenLoc((*writtenRegs.begin())->getID());
1768
1769    // Handle memory loads
1770    if (insn->readsMemory()) {
1771       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1772          operands[1].format(arch).c_str());
1773
1774       // Extract the expression inside the dereference
1775       std::vector<Expression::Ptr> addrExpr;
1776       operands[1].getValue()->getChildren(addrExpr);
1777       assert(addrExpr.size() == 1);
1778
1779       // Try to determine the read memory address
1780       StateEvalVisitor visitor;
1781       if (intervals_ == NULL) {
1782          visitor = StateEvalVisitor(off, insn, NULL);
1783       } else {
1784          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1785       }
1786       addrExpr[0]->apply(&visitor);
1787       if (visitor.isDefined()) {
1788          // We can track the memory location we're loading from
1789          std::pair<Address, bool> resultPair = visitor.getResult();
1790          Absloc readLoc;
1791          if (resultPair.second) {
1792             // We have a stack slot
1793             readLoc = Absloc(resultPair.first, 0, NULL);
1794          } else {
1795             // We have a static address
1796             readLoc = Absloc(resultPair.first);
1797          }
1798          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1799             readLoc.format().c_str());
1800          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1801       } else {
1802          // We can't track this memory location
1803          stackanalysis_printf("\t\t\tCan't determine location\n");
1804          xferFuncs.push_back(TransferFunc::retopFunc(writtenLoc));
1805       }
1806       return;
1807    }
1808
1809    assert(readRegs.size() == 1);
1810    Absloc readLoc((*readRegs.begin())->getID());
1811
1812    stackanalysis_printf("\t\t\tCopy detected: %s -> %s\n",
1813       readLoc.format().c_str(), writtenLoc.format().c_str());
1814    xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc));
1815 }
1816
1817 void StackAnalysis::handleSignExtend(Instruction::Ptr insn, Block *block,
1818    const Offset off, TransferFuncs &xferFuncs) {
1819    // This instruction sign extends the read register into the written
1820    // register. Copying insn't really correct here...sign extension is going
1821    // to change the value...
1822
1823    // In x86/x86_64, sign extends can't write to memory
1824    assert(!insn->writesMemory());
1825
1826    Architecture arch = insn->getArch();  // Needed for debug messages
1827
1828    // Extract operands
1829    std::vector<Operand> operands;
1830    insn->getOperands(operands);
1831    assert(operands.size() == 2);
1832
1833    // Extract written/read register sets
1834    std::set<RegisterAST::Ptr> writtenRegs;
1835    std::set<RegisterAST::Ptr> readRegs;
1836    operands[0].getWriteSet(writtenRegs);
1837    operands[1].getReadSet(readRegs);
1838
1839    assert(writtenRegs.size() == 1);
1840    Absloc writtenLoc((*writtenRegs.begin())->getID());
1841
1842    // Handle memory loads
1843    if (insn->readsMemory()) {
1844       stackanalysis_printf("\t\t\tMemory read from: %s\n",
1845          operands[1].format(arch).c_str());
1846
1847       // Extract the expression inside the dereference
1848       std::vector<Expression::Ptr> addrExpr;
1849       operands[1].getValue()->getChildren(addrExpr);
1850       assert(addrExpr.size() == 1);
1851
1852       // Try to determine the read memory address
1853       StateEvalVisitor visitor;
1854       if (intervals_ == NULL) {
1855          visitor = StateEvalVisitor(off, insn, NULL);
1856       } else {
1857          visitor = StateEvalVisitor(off, insn, &(*intervals_)[block][off]);
1858       }
1859       addrExpr[0]->apply(&visitor);
1860       if (visitor.isDefined()) {
1861          // We can track the memory location we're loading from
1862          std::pair<Address, bool> resultPair = visitor.getResult();
1863          Absloc readLoc;
1864          if (resultPair.second) {
1865             // We have a stack slot
1866             readLoc = Absloc(resultPair.first, 0, NULL);
1867          } else {
1868             // We have a static address
1869             readLoc = Absloc(resultPair.first);
1870          }
1871          stackanalysis_printf("\t\t\tEvaluates to: %s\n",
1872             readLoc.format().c_str());
1873          xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc,
1874             true));
1875       } else {
1876          // We can't track this memory location
1877          stackanalysis_printf("\t\t\tCan't determine location\n");
1878          xferFuncs.push_back(TransferFunc::retopFunc(writtenLoc));
1879       }
1880       return;
1881    }
1882
1883    assert(readRegs.size() == 1);
1884    Absloc readLoc((*readRegs.begin())->getID());
1885
1886    stackanalysis_printf(
1887       "\t\t\t Sign extend insn detected: %s -> %s (must be top or bottom)\n",
1888       readLoc.format().c_str(), writtenLoc.format().c_str());
1889    xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc, true));
1890 }
1891
1892 void StackAnalysis::handleSpecialSignExtend(Instruction::Ptr insn,
1893    TransferFuncs &xferFuncs) {
1894    // This instruction sign extends the read register into the written
1895    // register. Copying insn't really correct here...sign extension is going
1896    // to change the value...
1897
1898    // Extract written/read register sets
1899    std::set<RegisterAST::Ptr> writtenRegs;
1900    insn->getWriteSet(writtenRegs);
1901    assert(writtenRegs.size() == 1);
1902    MachRegister writtenReg = (*writtenRegs.begin())->getID();
1903    MachRegister readReg;
1904    if (writtenReg == x86_64::rax) readReg = x86_64::eax;
1905    else if (writtenReg == x86_64::eax) readReg = x86_64::ax;
1906    else if (writtenReg == x86_64::ax) readReg = x86_64::al;
1907    else if (writtenReg == x86::eax) readReg = x86::ax;
1908    else if (writtenReg == x86::ax) readReg = x86::al;
1909    else assert(false);
1910
1911    Absloc writtenLoc(writtenReg);
1912    Absloc readLoc(readReg);
1913
1914    stackanalysis_printf(
1915       "\t\t\t Special sign extend detected: %s -> %s (must be top/bottom)\n",
1916       readLoc.format().c_str(), writtenLoc.format().c_str());
1917    xferFuncs.push_back(TransferFunc::copyFunc(readLoc, writtenLoc, true));
1918 }
1919
1920 void StackAnalysis::handleDefault(Instruction::Ptr insn,
1921    TransferFuncs &xferFuncs) {
1922
1923    std::set<RegisterAST::Ptr> written;
1924    insn->getWriteSet(written);
1925    for (std::set<RegisterAST::Ptr>::iterator iter = written.begin(); 
1926         iter != written.end(); ++iter) {
1927
1928       Absloc loc((*iter)->getID());
1929       xferFuncs.push_back(TransferFunc::copyFunc(loc, loc, true));
1930       stackanalysis_printf(
1931          "\t\t\t Unhandled insn %s detected: %s set to topBottom\n",
1932          insn->format().c_str(), (*iter)->getID().name().c_str());
1933    }
1934    return;
1935 }
1936
1937 bool StackAnalysis::isCall(Instruction::Ptr insn) {
1938    return insn->getCategory() == c_CallInsn;
1939 }
1940
1941 bool StackAnalysis::handleNormalCall(Instruction::Ptr insn, Block *block,
1942    Offset off, TransferFuncs &xferFuncs) {
1943
1944    if (!insn->getControlFlowTarget()) return false;
1945
1946    // Must be a thunk based on parsing.
1947    if (off != block->lastInsnAddr()) return false;
1948    
1949    // Top caller-save registers
1950    // Bottom return registers
1951    ABI* abi = ABI::getABI(word_size);
1952    const bitArray callWritten = abi->getCallWrittenRegisters();
1953    const bitArray returnRegs = abi->getReturnRegisters();
1954    for (auto iter = abi->getIndexMap()->begin();
1955         iter != abi->getIndexMap()->end();
1956         ++iter) {
1957        // We only care about GPRs right now
1958       unsigned int gpr;
1959       Architecture arch = insn->getArch();
1960       switch(arch) {
1961          case Arch_x86:
1962             gpr = x86::GPR;
1963             break;
1964          case Arch_x86_64:
1965             gpr = x86_64::GPR;
1966             break;
1967          case Arch_ppc32:
1968             gpr = ppc32::GPR;
1969             break;
1970          case Arch_ppc64:
1971             gpr = ppc64::GPR;
1972             break;
1973          default:
1974             handleDefault(insn, xferFuncs);
1975             return true;
1976       }
1977       if ((*iter).first.regClass() == gpr) {
1978          if (callWritten.test((*iter).second)) {
1979             Absloc loc((*iter).first);
1980             if (returnRegs.test((*iter).second)) {
1981                // Bottom
1982                xferFuncs.push_back(TransferFunc::bottomFunc(loc));
1983             } else {
1984                // Top
1985                xferFuncs.push_back(TransferFunc::retopFunc(loc));
1986             }
1987          }
1988       }
1989    }
1990
1991    const Block::edgelist & outs = block->targets();  
1992    Block::edgelist::const_iterator eit = outs.begin();
1993    for ( ; eit != outs.end(); ++eit) {
1994       Edge *cur_edge = (Edge*)*eit;
1995
1996       Absloc sploc(sp());
1997
1998       if (cur_edge->type() == DIRECT) {
1999          // For some reason we're treating this
2000          // call as a branch. So it shifts the stack
2001          // like a push (heh) and then we're done.
2002          stackanalysis_printf(
2003             "\t\t\t Stack height changed by simulate-jump call\n");
2004          xferFuncs.push_back(TransferFunc::deltaFunc(sploc, -1 * word_size));
2005          return true;
2006       }
2007       
2008       if (cur_edge->type() != CALL) 
2009          continue;
2010       
2011       Block *target_bbl = cur_edge->trg();
2012       Function *target_func = target_bbl->obj()->findFuncByEntry(
2013          target_bbl->region(), target_bbl->start());
2014       
2015       if (!target_func)
2016          continue;
2017       
2018       Height h = getStackCleanAmount(target_func);
2019       if (h == Height::bottom) {
2020          stackanalysis_printf(
2021             "\t\t\t Stack height changed by self-cleaning function: bottom\n");
2022          xferFuncs.push_back(TransferFunc::bottomFunc(sploc));
2023       }
2024       else {
2025          stackanalysis_printf(
2026             "\t\t\t Stack height changed by self-cleaning function: %ld\n",
2027             h.height());
2028          xferFuncs.push_back(TransferFunc::deltaFunc(sploc, h.height()));
2029       }
2030       return true;
2031
2032    }
2033    stackanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
2034    return true;
2035 }
2036                                        
2037
2038 bool StackAnalysis::handleThunkCall(Instruction::Ptr insn,
2039    TransferFuncs &xferFuncs) {
2040
2041    // We know that we're not a normal call, so it depends on whether the CFT is
2042    // "next instruction" or not.
2043    if (insn->getCategory() != c_CallInsn || !insn->getControlFlowTarget()) {
2044       return false;
2045    }
2046
2047    // Eval of getCFT(0) == size?
2048    Expression::Ptr cft = insn->getControlFlowTarget();
2049    cft->bind(thePC.get(), Result(u32, 0));
2050    Result res = cft->eval();
2051    if (!res.defined) return false;
2052    if (res.convert<unsigned>() == insn->size()) {
2053       Absloc sploc(sp());
2054       xferFuncs.push_back(TransferFunc::deltaFunc(sploc, -1 * word_size));
2055       return true;
2056    }
2057    // Else we're calling a mov, ret thunk that has no effect on the stack
2058    // pointer
2059    return true;
2060 }
2061
2062
2063 void StackAnalysis::createEntryInput(AbslocState &input) {
2064    // FIXME for POWER/non-IA32
2065    // IA32 - the in height includes the return address and therefore
2066    // is <wordsize>
2067    // POWER - the in height is 0
2068 #if defined(arch_power)
2069    input[Absloc(sp())] = Height(0);
2070 #elif (defined(arch_x86) || defined(arch_x86_64))
2071    input[Absloc(sp())] = Height(-1 * word_size);
2072 #else
2073    assert(0 && "Unimplemented architecture");
2074 #endif
2075 }
2076
2077 void StackAnalysis::createSummaryEntryInput(TransferSet &input) {
2078    // Get a set of all input locations
2079    std::set<Absloc> inputLocs;
2080    for (auto beIter = blockEffects->begin(); beIter != blockEffects->end();
2081       beIter++) {
2082       const SummaryFunc &sf = beIter->second;
2083       const TransferSet &af = sf.accumFuncs;
2084       for (auto afIter = af.begin(); afIter != af.end(); afIter++) {
2085          const TransferFunc &tf = afIter->second;
2086          if (tf.target.isValid()) {
2087             inputLocs.insert(tf.target);
2088          }
2089          if (tf.from.isValid()) {
2090             inputLocs.insert(tf.from);
2091          }
2092          if (!tf.fromRegs.empty()) {
2093             for (auto frIter = tf.fromRegs.begin(); frIter != tf.fromRegs.end();
2094                frIter++) {
2095                Absloc deploc = frIter->first;
2096                inputLocs.insert(deploc);
2097             }
2098          }
2099       }
2100    }
2101
2102    // Create identity functions for each input location
2103    for (auto locIter = inputLocs.begin(); locIter != inputLocs.end();
2104       locIter++) {
2105       const Absloc &loc = *locIter;
2106       input[loc] = TransferFunc::identityFunc(loc);
2107    }
2108 }
2109
2110
2111 StackAnalysis::AbslocState StackAnalysis::getSrcOutputLocs(Edge* e) {
2112    Block* b = e->src();
2113    stackanalysis_printf("%lx ", b->lastInsnAddr());
2114    return blockOutputs[b];
2115 }
2116
2117 StackAnalysis::TransferSet StackAnalysis::getSummarySrcOutputLocs(Edge* e) {
2118    Block* b = e->src();
2119    stackanalysis_printf("%lx ", b->lastInsnAddr());
2120    return blockSummaryOutputs[b];
2121 }
2122
2123 void StackAnalysis::meetInputs(Block *block, AbslocState& blockInput,
2124    AbslocState &input) {
2125
2126    input.clear();
2127
2128    //Intraproc epred; // ignore calls, returns in edge iteration
2129    //NoSinkPredicate epred2(&epred); // ignore sink node (unresolvable)
2130    intra_nosink epred2;
2131
2132    stackanalysis_printf("\t ... In edges: ");
2133    const Block::edgelist & inEdges = block->sources();
2134    std::for_each(
2135       boost::make_filter_iterator(epred2, inEdges.begin(), inEdges.end()),
2136       boost::make_filter_iterator(epred2, inEdges.end(), inEdges.end()),
2137       boost::bind(&StackAnalysis::meet, this,
2138          boost::bind(&StackAnalysis::getSrcOutputLocs, this, _1),
2139          boost::ref(input)));
2140    stackanalysis_printf("\n");
2141
2142    meet(blockInput, input);
2143 }
2144
2145
2146 void StackAnalysis::meetSummaryInputs(Block *block, TransferSet &blockInput,
2147    TransferSet &input) {
2148
2149    input.clear();
2150
2151    //Intraproc epred; // ignore calls, returns in edge iteration
2152    //NoSinkPredicate epred2(&epred); // ignore sink node (unresolvable)
2153    intra_nosink epred2;
2154
2155    stackanalysis_printf("\t ... In edges: ");
2156    const Block::edgelist & inEdges = block->sources();
2157    std::for_each(
2158       boost::make_filter_iterator(epred2, inEdges.begin(), inEdges.end()),
2159       boost::make_filter_iterator(epred2, inEdges.end(), inEdges.end()),
2160       boost::bind(&StackAnalysis::meetSummary, this,
2161          boost::bind(&StackAnalysis::getSummarySrcOutputLocs, this, _1),
2162          boost::ref(input)));
2163    stackanalysis_printf("\n");
2164
2165    meetSummary(blockInput, input);
2166 }
2167
2168 void StackAnalysis::meet(const AbslocState &input, AbslocState &accum) {
2169    for (AbslocState::const_iterator iter = input.begin();
2170       iter != input.end(); ++iter) {
2171       accum[iter->first] = Height::meet(iter->second, accum[iter->first]);
2172       if (accum[iter->first].isTop()) {
2173          accum.erase(iter->first);
2174       }
2175    }
2176 }
2177
2178
2179 void StackAnalysis::meetSummary(const TransferSet &input, TransferSet &accum) {
2180    for (auto iter = input.begin(); iter != input.end(); ++iter) {
2181       const Absloc &loc = iter->first;
2182       const TransferFunc &inputFunc = iter->second;
2183       accum[loc] = TransferFunc::meet(inputFunc, accum[loc]);
2184       if (accum[loc].isTop() && !accum[loc].isRetop()) {
2185          accum.erase(loc);
2186       }
2187    }
2188 }
2189
2190
2191 StackAnalysis::Height &StackAnalysis::Height::operator+=(const Height &other) {
2192    if (isBottom()) return *this;
2193    if (other.isBottom()) {
2194       *this = bottom;
2195       return *this;
2196    }
2197    if (isTop() && other.isTop()) {
2198       // TOP + TOP = TOP
2199       *this = top;
2200       return *this;
2201    }
2202    if (isTop() || other.isTop()) {
2203       // TOP + height = BOTTOM
2204       *this = bottom;
2205       return *this;
2206    }
2207
2208    height_ += other.height_;
2209    return *this;
2210 }
2211
2212 StackAnalysis::Height &StackAnalysis::Height::operator+=(
2213    const signed long &rhs) {
2214    if (isBottom()) return *this;
2215    if (isTop()) return *this;
2216
2217    height_ += rhs;
2218    return *this;
2219 }
2220
2221 const StackAnalysis::Height StackAnalysis::Height::operator+(const Height &rhs)
2222    const {
2223    if (isBottom()) return bottom;
2224    if (rhs.isBottom()) return rhs;
2225    if (isTop() && rhs.isTop()) return top;
2226    if (isTop() || rhs.isTop()) return bottom;
2227    return Height(height_ + rhs.height_);
2228 }
2229
2230 const StackAnalysis::Height StackAnalysis::Height::operator+(
2231    const signed long &rhs) const {
2232    if (isBottom()) return bottom;
2233    if (isTop()) return top;
2234    return Height(height_ + rhs);
2235 }
2236
2237 const StackAnalysis::Height StackAnalysis::Height::operator-(const Height &rhs)
2238    const {
2239    if (isBottom()) return bottom;
2240    if (rhs.isBottom()) return rhs;
2241    if (isTop() && rhs.isTop()) return top;
2242    if (isTop() || rhs.isTop()) return bottom;
2243    return Height(height_ - rhs.height_);
2244 }
2245
2246
2247 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::identityFunc(
2248    Absloc r) {
2249    return copyFunc(r, r);
2250 }
2251
2252 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::deltaFunc(Absloc r,
2253    long d) {
2254    return TransferFunc(uninitialized, d, r, r);
2255 }
2256
2257 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::absFunc(Absloc r,
2258    long a, bool i) {
2259    return TransferFunc(a, 0, Absloc(), r, i);
2260 }
2261
2262 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::copyFunc(Absloc f,
2263    Absloc t, bool i) {
2264    return TransferFunc (uninitialized, 0, f, t, i);
2265 }
2266
2267 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::bottomFunc(Absloc r) {
2268    return TransferFunc(notUnique, notUnique, Absloc(), r, false, false, BOTTOM);
2269 }
2270
2271 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::retopFunc(Absloc r) {
2272    return TransferFunc(uninitialized, 0, Absloc(), r, false, true, TOP);
2273 }
2274
2275 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::sibFunc(
2276    std::map<Absloc, std::pair<long,bool> > f, long d, Absloc t) {
2277    return TransferFunc(f, d, t);
2278 }
2279
2280 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::meet(
2281    const TransferFunc &lhs, const TransferFunc &rhs) {
2282    // Handle default-constructed TransferFuncs
2283    if (lhs.isTop() && !lhs.isRetop()) return rhs;
2284    if (rhs.isTop() && !rhs.isRetop()) return lhs;
2285
2286    assert(lhs.target == rhs.target);
2287    if (lhs == rhs) return lhs;
2288
2289    TransferFunc ret;
2290    if (lhs.isAbs()) {
2291       if (rhs.isAbs()) {
2292          // Since we know lhs != rhs, the abs values must be different
2293          ret = retopFunc(lhs.target);
2294       } else if (rhs.isCopy() || rhs.isBottom() || rhs.isRetop() ||
2295          rhs.isSIB()) {
2296          ret = rhs;
2297       } else {
2298          assert(false);
2299       }
2300    } else if (lhs.isCopy()) {
2301       if (rhs.isAbs()) {
2302          ret = lhs;
2303       } else if (rhs.isCopy()) {
2304          if (lhs.from == rhs.from) {
2305             // Same base register. Since we know lhs != rhs, either the deltas
2306             // are different or the topBottom values are different. Either way,
2307             // we need to return a function that is topBottom.
2308             ret = lhs;
2309             ret.topBottom = true;
2310             ret.delta = 0;
2311          } else {
2312             // Different base registers.  Use a SIB function to capture both
2313             // possible bases.  Note that current SIB function handling doesn't
2314             // actually add the terms together.
2315             // FIXME if SIB function handling changes.
2316             std::map<Absloc, std::pair<long, bool>> fromRegs;
2317             fromRegs[lhs.from] = std::make_pair(1, true);
2318             fromRegs[rhs.from] = std::make_pair(1, true);
2319             ret = sibFunc(fromRegs, 0, lhs.target);
2320          }
2321       } else if (rhs.isBottom()) {
2322          ret = rhs;
2323       } else if (rhs.isRetop()) {
2324          ret = lhs;
2325       } else if (rhs.isSIB()) {
2326          // Add the source register of the LHS copy to the RHS SIB function.
2327          // Note that current SIB function handling doesn't actually add the
2328          // terms together.
2329          // FIXME if SIB function handling changes.
2330          ret = rhs;
2331          ret.fromRegs[lhs.from] = std::make_pair(1, true);
2332       } else {
2333          assert(false);
2334       }
2335    } else if (lhs.isBottom()) {
2336       ret = lhs;
2337    } else if (lhs.isRetop()) {
2338       if (rhs.isAbs()) {
2339          ret = lhs;
2340       } else if (rhs.isCopy() || rhs.isBottom() || rhs.isRetop() ||
2341          rhs.isSIB()) {
2342          ret = rhs;
2343       } else {
2344          assert(false);
2345       }
2346    } else if (lhs.isSIB()) {
2347       if (rhs.isAbs()) {
2348          ret = lhs;
2349       } else if (rhs.isCopy()) {
2350          // Add the source register of the RHS copy to the LHS SIB function.
2351          // Note that current SIB function handling doesn't actually add the
2352          // terms together.
2353          // FIXME if SIB function handling changes.
2354          ret = lhs;
2355          ret.fromRegs[rhs.from] = std::make_pair(1, true);
2356       } else if (rhs.isBottom()) {
2357          ret = rhs;
2358       } else if (rhs.isRetop()) {
2359          ret = lhs;
2360       } else if (rhs.isSIB()) {
2361          if (lhs.fromRegs == rhs.fromRegs) {
2362             // Same SIB.  Since we know lhs != rhs, either the deltas are
2363             // different or the topBottom values are different.  Either way, we
2364             // need to return a function that is topBottom.
2365             ret = lhs;
2366             ret.topBottom = true;
2367             ret.delta = 0;
2368          } else {
2369             // Different SIBs.  Combine the terms of the LHS and RHS SIB
2370             // functions.  Note that current SIB function handling doesn't
2371             // actually add the terms together.
2372             // FIXME if SIB function handling changes.
2373             ret = lhs;
2374             for (auto iter = rhs.fromRegs.begin(); iter != rhs.fromRegs.end();
2375                iter++) {
2376                const Absloc &loc = iter->first;
2377                const std::pair<long, bool> &val = iter->second;
2378                auto findLoc = ret.fromRegs.find(loc);
2379                if (findLoc == ret.fromRegs.end() || (val.first == 1 &&
2380                   ret.fromRegs[loc].first != 1)) {
2381                   ret.fromRegs[loc] = val;
2382                }
2383             }
2384          }
2385       } else {
2386          assert(false);
2387       }
2388    } else {
2389       assert(false);
2390    }
2391    return ret;
2392 }
2393
2394
2395 bool StackAnalysis::TransferFunc::isIdentity() const {
2396    return isCopy() && from == target && delta == 0 && !topBottom;
2397 }
2398
2399 bool StackAnalysis::TransferFunc::isBottom() const {
2400    return type_ == BOTTOM;
2401 }
2402
2403 bool StackAnalysis::TransferFunc::isTop() const {
2404    return type_ == TOP;
2405 }
2406
2407 bool StackAnalysis::TransferFunc::isRetop() const {
2408    return isTop() && retop;
2409 }
2410
2411 bool StackAnalysis::TransferFunc::isCopy() const {
2412    return from.isValid();
2413 }
2414
2415 bool StackAnalysis::TransferFunc::isAbs() const {
2416    return !isTop() && !isBottom() && !isCopy() && !isSIB();
2417 }
2418
2419 bool StackAnalysis::TransferFunc::isDelta() const {
2420    return delta != 0;
2421 }
2422
2423 bool StackAnalysis::TransferFunc::isSIB() const {
2424     return (fromRegs.size() > 0);
2425 }
2426
2427
2428 // Destructive update of the input map. Assumes inputs are absolute,
2429 // uninitialized, or bottom; no deltas.
2430 StackAnalysis::Height StackAnalysis::TransferFunc::apply(
2431    const AbslocState &inputs) const {
2432    assert(target.isValid());
2433    // Bottom stomps everything
2434    if (isBottom()) {
2435       return Height::bottom;
2436    }
2437
2438    AbslocState::const_iterator iter = inputs.find(target);
2439    Height input;
2440    if (iter != inputs.end()) {
2441       input = iter->second;
2442    } else {
2443       input = Height::top;
2444    }
2445
2446    bool isTopBottomOrig = isTopBottom();
2447
2448    if (isSIB()) {
2449       input = Height::top; // SIB overwrites, so start at TOP
2450       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
2451          Absloc curLoc = (*iter).first;
2452          long curScale = (*iter).second.first;
2453          bool curTopBottom = (*iter).second.second;
2454          auto findLoc = inputs.find(curLoc);
2455          Height locInput;
2456          if (findLoc == inputs.end()) {
2457             locInput = Height::top;
2458          } else {
2459             locInput = findLoc->second;
2460          }
2461
2462          if (locInput == Height::top) {
2463             // This term doesn't affect our end result, so it can be safely
2464             // ignored.
2465          } else if (locInput == Height::bottom) {
2466             if (curScale == 1) {
2467                // Must bottom everything only if the scale is 1.  Otherwise,
2468                // any stack height will be obfuscated.
2469                input = Height::bottom;
2470                break;
2471             }
2472          } else {
2473             if (curScale == 1) {
2474                // If the scale isn't 1, then any stack height is obfuscated,
2475                // and we can safely ignore the term.
2476                if (curTopBottom) {
2477                   input = Height::bottom;
2478                   break;
2479                } else {
2480                   input += locInput; // Matt: Always results in bottom?
2481                }
2482             }
2483          }
2484       }
2485    }
2486
2487    if (isAbs()) {
2488       // We cannot be a copy, as the absolute removes that.
2489       assert(!isCopy());
2490       // Apply the absolute
2491       // NOTE: an absolute is not a stack height, set input to top
2492       //input = abs;
2493       input = Height::top;
2494    }
2495    if (isCopy()) {
2496       // Cannot be absolute
2497       assert(!isAbs());
2498       // Copy the input value from whatever we're a copy of.
2499       AbslocState::const_iterator iter2 = inputs.find(from);
2500       if (iter2 != inputs.end()) input = iter2->second;
2501       else input = Height::top;
2502    }
2503    if (isDelta()) {
2504       input += delta;
2505    }
2506    if (isRetop()) {
2507       input = Height::top;
2508    }
2509    if (isTopBottomOrig) {
2510       if (!input.isTop()) {
2511          input = Height::bottom;
2512       }
2513    }
2514    return input;
2515 }
2516
2517 // Returns accumulated transfer function without modifying inputs
2518 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::summaryAccumulate(
2519    const TransferSet &inputs) const {
2520    TransferFunc input;
2521    auto findTarget = inputs.find(target);
2522    if (findTarget != inputs.end()) {
2523       input = findTarget->second;
2524    }
2525    if (input.target.isValid()) assert(input.target == target);
2526    input.target = target; // Default constructed TransferFuncs won't have this
2527    assert(target.isValid());
2528
2529    // Bottom stomps everything
2530    if (isBottom()) {
2531       input = bottomFunc(target);
2532       return input;
2533    }
2534    bool isTopBottomOrig = isTopBottom();
2535    if (!input.isTopBottom() && !input.isRetop()) {
2536       input.topBottom = isTopBottomOrig;
2537    }
2538    // Absolutes override everything else
2539    if (isAbs()) {
2540       input = absFunc(target, abs, false);
2541       return input;
2542    }
2543    if (isSIB()) {
2544       // First check for special cases
2545       bool allAbs = true;
2546       bool allToppable = true;
2547       bool anyBottomed = false;
2548       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); iter++) {
2549          Absloc fromLocOrig = iter->first;
2550          long scaleOrig = iter->second.first;
2551          auto inputEntry = inputs.find(fromLocOrig);
2552          if (inputEntry == inputs.end()) {
2553             allAbs = false;
2554             if (scaleOrig == 1) {
2555                allToppable = false;
2556             }
2557          } else {
2558             if (inputEntry->second.isBottom() && scaleOrig == 1) {
2559                anyBottomed = true;
2560             }
2561             if (!inputEntry->second.isRetop() && !inputEntry->second.isAbs() &&
2562                scaleOrig == 1) {
2563                allToppable = false;
2564             }
2565             if (!inputEntry->second.isAbs()) {
2566                allAbs = false;
2567             }
2568          }
2569       }
2570
2571       // Now handle special cases
2572       if (anyBottomed) {
2573          input = bottomFunc(target);
2574          return input;
2575       }
2576       if (allAbs) {
2577          long newDelta = delta;
2578          for (auto iter = fromRegs.begin(); iter != fromRegs.end(); iter++) {
2579             Absloc fromLocOrig = iter->first;
2580             long scaleOrig = iter->second.first;
2581             TransferFunc inputAbsFunc = inputs.find(fromLocOrig)->second;
2582             newDelta += inputAbsFunc.abs * scaleOrig;
2583          }
2584          input = absFunc(target, newDelta);
2585          return input;
2586       }
2587       if (allToppable) {
2588          input = retopFunc(target);
2589          return input;
2590       }
2591
2592       // Handle default case
2593       std::map<Absloc, std::pair<long,bool> > newFromRegs;
2594       bool anyToppedTerms = false;
2595       for (auto iter = fromRegs.begin(); iter != fromRegs.end(); ++iter) {
2596          Absloc fromLocOrig = (*iter).first;
2597          long scaleOrig = (*iter).second.first;
2598
2599          // Because any term with a scale != 1 is TOP, such terms do not affect
2600          // the final TOP/BOTTOM/Height value of the LEA and can be ignored.
2601          // FIXME if we change apply() to include constant propagation
2602          if (scaleOrig != 1) {
2603             anyToppedTerms = true;
2604             continue;
2605          }
2606
2607          auto findLoc = inputs.find(fromLocOrig);
2608          if (findLoc == inputs.end()) {
2609             // Easy case
2610             // Only add the term if we're not already tracking that register.
2611             // FIXME if we change apply() to include constant propagation
2612             auto found = newFromRegs.find(fromLocOrig);
2613             if (found == newFromRegs.end()) {
2614                newFromRegs.insert(make_pair(fromLocOrig,
2615                   make_pair(scaleOrig, false)));
2616             }
2617          } else {
2618             TransferFunc fromRegFunc = findLoc->second;
2619             assert(!fromRegFunc.isBottom());  // Should be special case
2620             if (fromRegFunc.isSIB()) {
2621                // Replace registers and update scales
2622                for (auto regIter = fromRegFunc.fromRegs.begin();
2623                   regIter != fromRegFunc.fromRegs.end(); ++regIter) {
2624                   Absloc replaceLoc = regIter->first;
2625                   long replaceScale = regIter->second.first;
2626                   bool replaceTopBottom = regIter->second.second;
2627                   long newScale = replaceScale * scaleOrig;
2628
2629                   // Add to our map only the registers that we aren't already
2630                   // considering.
2631                   // FIXME if we change apply() to include constant propagation
2632                   auto found = newFromRegs.find(replaceLoc);
2633                   if (found == newFromRegs.end()) {
2634                      newFromRegs.insert(make_pair(replaceLoc,
2635                         make_pair(newScale, replaceTopBottom)));
2636                   }
2637                }
2638             }
2639             if (fromRegFunc.isCopy()) {
2640                // Replace fromRegOrig with fromRegFunc.from only if we aren't
2641                // already considering fromRegFunc.from in our map.
2642                // FIXME if we change apply() to include constant propagation
2643                auto found = newFromRegs.find(fromRegFunc.from);
2644                if (found == newFromRegs.end()) {
2645                   newFromRegs.insert(make_pair(fromRegFunc.from,
2646                      make_pair(scaleOrig, fromRegFunc.isTopBottom())));
2647                }
2648             }
2649             if (fromRegFunc.isDelta()) {
2650                if (!fromRegFunc.isCopy() && !fromRegFunc.isSIB() &&
2651                   !fromRegFunc.isAbs()) {
2652                   // Add the register back in...
2653                   // FIXME if we change apply() to include constant propagation
2654                   auto found = newFromRegs.find(fromLocOrig);
2655                   if (found == newFromRegs.end()) {
2656                      newFromRegs.insert(make_pair(fromLocOrig,
2657                         make_pair(scaleOrig, fromRegFunc.isTopBottom())));
2658                   }
2659                }
2660             }
2661             if (fromRegFunc.isRetop()) {
2662                // This is a register that was re-topped due to an instruction
2663                // in this block.  Thus this term is TOP and doesn't affect the
2664                // value of the LEA, so we can ignore it.
2665                // FIXME if we change apply() to include constant propagation
2666                anyToppedTerms = true;
2667                continue;
2668             }
2669             if (fromRegFunc.isTop()) {
2670                // This is the default constructed target when the target didn't
2671                // already exist.  Keep track of this register unless we already
2672                // are.
2673                // FIXME if we change apply() to include constant propagation
2674                auto found = newFromRegs.find(fromLocOrig);
2675                if (found == newFromRegs.end()) {
2676                   newFromRegs.insert(make_pair(fromLocOrig,
2677                      make_pair(scaleOrig, false)));
2678                }
2679             }
2680          }
2681       }
2682
2683       if (anyToppedTerms) {
2684          // If any term is later discovered to be a stack height, we need to
2685          // bottom the target register since this SIB contains a topped term
2686          // (we know the topped term isn't a stack height, but we don't know
2687          // precisely what it is).  We indicate this by setting the
2688          // topBottom flag on non-topped registers.
2689          for (auto iter = newFromRegs.begin(); iter != newFromRegs.end();
2690             iter++) {
2691             iter->second.second = true;
2692          }
2693       }
2694
2695       input = sibFunc(newFromRegs, 0, target);
2696       input.topBottom = isTopBottomOrig;
2697       return input;
2698    }
2699
2700    // Copies can be tricky
2701    // apply copy logic only if registers are different
2702    if (isCopy()) {
2703       // We need to record that we want to take the inflow height
2704       // of a different register. 
2705       // Don't do an inputs[from] as that creates
2706       auto iter = inputs.find(from);
2707       if (iter == inputs.end()) {
2708          // Copying to something we haven't seen yet; easy
2709          input = *this;
2710          if (isTopBottomOrig) {
2711             input.topBottom = true;
2712             input.delta = 0;
2713          }
2714          return input;
2715       }
2716
2717       const TransferFunc &orig = iter->second;
2718
2719       if (orig.isAbs()) {
2720          // We reset the height, so we don't care about the inflow height
2721          assert(!orig.isCopy());
2722          input = orig;
2723          input.target = target;
2724          input.topBottom = false;
2725          assert(input.target.isValid());
2726
2727          if (isDelta()) {
2728             input.delta += delta;
2729          }
2730          return input;
2731       }
2732       if (orig.isCopy()) {
2733          assert(!orig.isAbs());
2734          input = orig;
2735          input.target = target;
2736          assert(input.target.isValid());
2737
2738          if (isDelta()) {
2739             input.delta += delta;
2740          }
2741          if (isTopBottomOrig || orig.isTopBottom()) {
2742             input.topBottom = true;
2743             input.delta = 0;
2744          }
2745          return input;
2746       }
2747       if (orig.isSIB()) {
2748          input = orig;
2749          input.target = target;
2750
2751          if (isDelta()) {
2752             input.delta += delta;
2753          }
2754          if (isTopBottomOrig || orig.isTopBottom()) {
2755             input.topBottom = true;
2756             input.delta = 0;
2757          }
2758          return input;
2759       }
2760
2761       // without bottom we mess up in the default case.
2762       if (orig.isBottom()) {
2763          input = bottomFunc(target);
2764          return input;
2765       }
2766
2767       if (orig.isRetop()) {
2768          input = retopFunc(target);
2769          return input;
2770       }
2771
2772       // Default case: record the copy, zero out everything else, copy over
2773       // the delta if it's defined.
2774       input.from = orig.target;
2775       input.abs = uninitialized;
2776       assert(!orig.isDelta());
2777       input.delta = 0;
2778       input.topBottom = isTopBottomOrig || orig.isTopBottom();
2779       input.fromRegs.clear();
2780    }
2781
2782    assert(!isDelta());
2783
2784    if (isRetop()) {
2785       input = *this;
2786    }
2787
2788    return input;
2789 }
2790
2791
2792 // Accumulation to the input map. This is intended to create a summary, so we
2793 // create something that can take further input.
2794 void StackAnalysis::TransferFunc::accumulate(TransferSet &inputs) {
2795    inputs[target] = summaryAccumulate(inputs);
2796 }
2797
2798
2799 void StackAnalysis::SummaryFunc::apply(const AbslocState &in,
2800    AbslocState &out) const {
2801
2802    // Copy all the elements we don't have xfer funcs for.
2803    out = in;
2804
2805    // Apply in parallel since all summary funcs are from the start of the block
2806    for (TransferSet::const_iterator iter = accumFuncs.begin();
2807       iter != accumFuncs.end(); ++iter) {
2808       assert(iter->first.isValid());
2809       out[iter->first] = iter->second.apply(in);
2810       if (out[iter->first].isTop()) {
2811          out.erase(iter->first);
2812       }
2813    }
2814 }
2815
2816
2817 void StackAnalysis::SummaryFunc::accumulate(const TransferSet &in,
2818    TransferSet &out) const {
2819
2820    // Copy all the elements we don't have xfer funcs for.
2821    out = in;
2822
2823    // Apply in parallel since all summary funcs are from the start of the block
2824    for (TransferSet::const_iterator iter = accumFuncs.begin();
2825       iter != accumFuncs.end(); ++iter) {
2826       assert(iter->first.isValid());
2827       out[iter->first] = iter->second.summaryAccumulate(in);
2828       if (out[iter->first].isTop() && !out[iter->first].isRetop()) {
2829          out.erase(iter->first);
2830       }
2831    }
2832 }
2833
2834 void StackAnalysis::SummaryFunc::add(TransferFuncs &xferFuncs) {
2835    // We need to update our register->xferFunc map
2836    // with the effects of each of the transferFuncs. 
2837    
2838    for (TransferFuncs::iterator iter = xferFuncs.begin(); 
2839         iter != xferFuncs.end(); ++iter) {
2840       TransferFunc &func = *iter;
2841
2842       func.accumulate(accumFuncs);
2843       validate();
2844    }
2845
2846 }
2847
2848 void StackAnalysis::SummaryFunc::validate() const {
2849    for (TransferSet::const_iterator iter = accumFuncs.begin(); 
2850       iter != accumFuncs.end(); ++iter) {
2851       const TransferFunc &func = iter->second;
2852       assert(func.target.isValid());
2853       if (func.isCopy()) assert(!func.isAbs());
2854       if (func.isAbs()) assert(!func.isCopy());
2855       if (func.isBottom()) assert(!func.isCopy());
2856    }
2857 }
2858
2859 MachRegister StackAnalysis::sp() { 
2860    return MachRegister::getStackPointer(func->isrc()->getArch());
2861 }
2862
2863 MachRegister StackAnalysis::fp() { 
2864    return MachRegister::getFramePointer(func->isrc()->getArch());
2865 }
2866
2867 std::string StackAnalysis::format(const AbslocState &input) const {
2868    std::stringstream ret;
2869    for (AbslocState::const_iterator iter = input.begin();
2870       iter != input.end(); ++iter) {
2871       ret << iter->first.format() << " := " << iter->second.format() << ", ";
2872    }
2873    return ret.str();
2874 }
2875
2876 std::string StackAnalysis::format(const TransferSet &input) const {
2877    std::stringstream ret;
2878    for (auto iter = input.begin(); iter != input.end(); ++iter) {
2879       ret << iter->second.format() << ", ";
2880    }
2881    return ret.str();
2882 }
2883
2884
2885 // Converts a delta in a Result to a long
2886 long StackAnalysis::extractDelta(Result deltaRes) {
2887    long delta;
2888    switch(deltaRes.size()) {
2889       case 1:
2890          delta = (long)deltaRes.convert<int8_t>();
2891          break;
2892       case 2:
2893          delta = (long)deltaRes.convert<int16_t>();
2894          break;
2895       case 4:
2896          delta = (long)deltaRes.convert<int32_t>();
2897          break;
2898       case 8:
2899          delta = (long)deltaRes.convert<int64_t>();
2900          break;
2901       default:
2902          assert(0);
2903    }
2904    return delta;
2905 }