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