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