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