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