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