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