Updated StackAnalysis::handleAddSub to also operate on non-SP registers.
[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
35 #include <queue>
36 #include <vector>
37 #include <boost/bind.hpp>
38
39 #include "ABI.h"
40 #include "stackanalysis.h"
41
42 #include "Annotatable.h"
43
44 #include "debug_dataflow.h"
45
46 #include "parseAPI/h/CFG.h"
47 #include "parseAPI/h/CodeObject.h"
48
49 using namespace Dyninst;
50 using namespace InstructionAPI;
51 using namespace Dyninst::ParseAPI;
52
53 const StackAnalysis::Height StackAnalysis::Height::bottom(StackAnalysis::Height::notUnique);
54 const StackAnalysis::Height StackAnalysis::Height::top(StackAnalysis::Height::uninitialized);
55
56 AnnotationClass <StackAnalysis::Intervals> Stack_Anno(std::string("Stack_Anno"));
57
58
59 //
60 //
61 // Concepts:
62 //
63 // There are three terms we throw around:
64 // 
65 // Stack height: the size of the stack; (cur_stack_ptr - func_start_stack_ptr)
66 // Stack delta: the difference in the size of the stack over the execution of
67 //   a region of code (basic block here). (block_end_stack_ptr - block_start_stack_ptr)
68 // Stack clean: the amount the callee function shifts the stack. This is an x86 idiom.
69 //   On x86 the caller pushes arguments onto the stack (and thus shifts the stack).
70 //   Normally the caller also cleans the stack (that is, removes arguments). However, 
71 //   some callee functions perform this cleaning themselves. We need to account for this
72 //   in our analysis, which otherwise assumes that callee functions don't alter the stack.
73 // 
74
75 bool StackAnalysis::analyze()
76 {
77
78   df_init_debug();
79
80   stackanalysis_printf("Beginning stack analysis for function %s\n",
81                        func->name().c_str());
82
83     stackanalysis_printf("\tSummarizing block effects\n");
84     summarizeBlocks();
85     
86     stackanalysis_printf("\tPerforming fixpoint analysis\n");
87     fixpoint();
88
89     stackanalysis_printf("\tCreating SP interval tree\n");
90     summarize();
91
92     func->addAnnotation(intervals_, Stack_Anno);
93
94     if (df_debug_stackanalysis) {
95         debug();
96     }
97
98     stackanalysis_printf("Finished stack analysis for function %s\n",
99                          func->name().c_str());
100    return true;
101 }
102
103 // We want to create a transfer function for the block as a whole. 
104 // This will allow us to perform our fixpoint calculation over
105 // blocks (thus, O(B^2)) rather than instructions (thus, O(I^2)). 
106 //
107 // Handling the stack height is straightforward. We also accumulate
108 // region changes in terms of a stack of Region objects.
109
110 typedef std::vector<std::pair<Instruction::Ptr, Offset> > InsnVec;
111
112 static void getInsnInstances(Block *block,
113                              InsnVec &insns) {
114   Offset off = block->start();
115   const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
116   if (ptr == NULL) return;
117   InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
118   while (off < block->end()) {
119     insns.push_back(std::make_pair(d.decode(), off));
120     off += insns.back().first->size();
121   }
122 }
123
124 void StackAnalysis::summarizeBlocks() {
125   Function::blocklist bs(func->blocks());
126   Function::blocklist::iterator bit = bs.begin();
127   for( ; bit != bs.end(); ++bit) {
128     Block *block = *bit;
129   
130     // Accumulators. They have the following behavior:
131     // 
132     // New region: add to the end of the regions list
133     // Offset to stack pointer: accumulate to delta.
134     // Setting the stack pointer: zero delta, set set_value.
135     // 
136     
137     SummaryFunc &bFunc = blockEffects[block];
138     
139     stackanalysis_printf("\t Block starting at 0x%lx: %s\n", 
140                          block->start(),
141                          bFunc.format().c_str());
142     InsnVec instances;
143     getInsnInstances(block, instances);
144     
145     for (unsigned j = 0; j < instances.size(); j++) {
146       InstructionAPI::Instruction::Ptr insn = instances[j].first;
147       Offset &off = instances[j].second;
148
149       // Fills in insnEffects[off]
150       TransferFuncs &xferFuncs = insnEffects[block][off];
151
152       computeInsnEffects(block, insn, off,
153                          xferFuncs);
154       bFunc.add(xferFuncs);
155
156       stackanalysis_printf("\t\t\t At 0x%lx:  %s\n",
157                                        off, bFunc.format().c_str());
158     }
159     stackanalysis_printf("\t Block summary for 0x%lx: %s\n", block->start(), bFunc.format().c_str());
160   }
161 }
162
163 struct intra_nosink : public ParseAPI::EdgePredicate
164 {
165   virtual bool operator()(Edge* e)
166   {
167     static Intraproc i;
168     static NoSinkPredicate n;
169     
170     return i(e) && n(e);
171   }
172   
173 };
174
175 void add_target(std::queue<Block*>& worklist, Edge* e)
176 {
177         worklist.push(e->trg());
178 }
179
180 void StackAnalysis::fixpoint() {
181   std::queue<Block *> worklist;
182   
183   //Intraproc epred; // ignore calls, returns in edge iteration
184   //NoSinkPredicate nosink(); // ignore sink node (unresolvable)
185   intra_nosink epred2;
186   
187   
188
189   worklist.push(func->entry());
190
191   Block *entry = func->entry();
192   
193   while (!worklist.empty()) {
194     Block *block = worklist.front();
195     stackanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n", block->start());
196     
197     worklist.pop();
198     
199     // Step 1: calculate the meet over the heights of all incoming
200     // intraprocedural blocks.
201     
202     RegisterState input;
203     
204     if (block == entry) {
205        createEntryInput(input);
206        stackanalysis_printf("\t Primed initial block\n");
207     }
208     else {
209         stackanalysis_printf("\t Calculating meet with block [%x-%x]\n", block->start(), block->lastInsnAddr());
210        meetInputs(block, blockInputs[block], input);
211     }
212     
213     stackanalysis_printf("\t New in meet: %s\n", format(input).c_str());
214
215     // Step 2: see if the input has changed
216     
217     if (input == blockInputs[block]) {
218        // No new work here
219        stackanalysis_printf("\t ... equal to current, skipping block\n");
220        continue;
221     }
222     
223     stackanalysis_printf("\t ... inequal to current %s, analyzing block\n", format(blockInputs[block]).c_str());
224     
225     blockInputs[block] = input;
226     
227     // Step 3: calculate our new outs
228     
229     blockEffects[block].apply(input,
230                               blockOutputs[block]);
231     
232     stackanalysis_printf("\t ... output from block: %s\n", format(blockOutputs[block]).c_str());
233     
234     // Step 4: push all children on the worklist.
235     
236     const Block::edgelist & outEdges = block->targets();
237     std::for_each(boost::make_filter_iterator(epred2, outEdges.begin(), outEdges.end()),
238                   boost::make_filter_iterator(epred2, outEdges.end(), outEdges.end()),
239                   boost::bind(add_target, boost::ref(worklist), _1));    
240   }
241 }
242
243
244
245 void StackAnalysis::summarize() {
246         // Now that we know the actual inputs to each block,
247         // we create intervals by replaying the effects of each
248         // instruction. 
249
250         intervals_ = new Intervals();
251
252         Function::blocklist bs = func->blocks();
253         Function::blocklist::iterator bit = bs.begin();
254         for( ; bit != bs.end(); ++bit) {
255                 Block *block = *bit;
256                 RegisterState input = blockInputs[block];
257
258                 for (std::map<Offset, TransferFuncs>::iterator iter = insnEffects[block].begin(); 
259                         iter != insnEffects[block].end(); ++iter) {
260                         Offset off = iter->first;
261                         TransferFuncs &xferFuncs = iter->second;
262
263                         // TODO: try to collapse these in some intelligent fashion
264                         (*intervals_)[block][off] = input;
265
266                         for (TransferFuncs::iterator iter2 = xferFuncs.begin();
267                                 iter2 != xferFuncs.end(); ++iter2) {
268                                         input[iter2->target] = iter2->apply(input);
269                         }
270                 }
271                 (*intervals_)[block][block->end()] = input;
272         assert(input == blockOutputs[block]);
273         }
274 }
275
276 void StackAnalysis::computeInsnEffects(ParseAPI::Block *block,
277                                        Instruction::Ptr insn,
278                                        const Offset off,
279                                        TransferFuncs &xferFuncs) {
280    stackanalysis_printf("\t\tInsn at 0x%lx\n", off);
281     
282     entryID what = insn->getOperation().getID();
283
284     // Reminder: what we're interested in:
285     // a) Use of the stack pointer to define another register
286     //      Assumption: this is done by an e_mov and is a direct copy
287     //                  else bottom
288     // b) Use of another register to define the stack pointer
289     //      Assumption: see ^^
290     // c) Modification of the stack pointer
291     // 
292     // The reason for these assumptions is to keep the analysis reasonable; also,
293     // other forms just don't occur. 
294     //
295     // In summary, the stack pointer must be read or written for us to be interested.
296     // 
297     // However, we need to detect when a register is destroyed. So if something is written,
298     // we assume it is destroyed.
299     // 
300     // For now, we assume an all-to-all mapping for speed. 
301
302     // Cases we handle
303     if (isCall(insn)) {
304        if (handleNormalCall(insn, block, off, xferFuncs))
305           return;
306        else if (handleThunkCall(insn, xferFuncs))
307           return;
308        else
309           return handleDefault(insn, xferFuncs);
310     }
311
312     int sign = 1;
313     switch (what) {
314        case e_push:
315           sign = -1;
316           //FALLTHROUGH
317        case e_pop:
318           handlePushPop(insn, sign, xferFuncs);
319           break;
320        case e_ret_near:
321        case e_ret_far:
322           handleReturn(insn, xferFuncs);
323           break;
324        case e_lea:
325          handleLEA(insn, xferFuncs);
326          break;
327        case e_sub:
328           sign = -1;
329           //FALLTHROUGH
330        case e_add:
331           handleAddSub(insn, sign, xferFuncs);
332           break;
333        case e_leave:
334           handleLeave(xferFuncs);
335           break;
336        case e_pushfd:
337           sign = -1;
338           //FALLTHROUGH
339        case e_popfd:
340           handlePushPopFlags(sign, xferFuncs);
341           break;
342        case e_pushad:
343            sign = -1;
344            handlePushPopRegs(sign, xferFuncs);
345            break;
346        case e_popad:
347            // This nukes all registers
348            handleDefault(insn, xferFuncs);
349            break;
350        case power_op_addi:
351        case power_op_addic:
352           handlePowerAddSub(insn, sign, xferFuncs);
353           break;
354        case power_op_stwu:
355           handlePowerStoreUpdate(insn, xferFuncs);
356           break;
357        case e_mov:
358           handleMov(insn, xferFuncs);
359           break;
360        case e_movzx:
361           handleZeroExtend(insn, xferFuncs);
362           break;
363        case e_movsx:
364        case e_movsxd:
365        case e_cbw:
366        case e_cwde:
367           handleSignExtend(insn, xferFuncs);
368           break;
369        default:
370           handleDefault(insn, xferFuncs);
371     }
372 }
373
374 StackAnalysis::Height StackAnalysis::getStackCleanAmount(Function *func) {
375     // Cache previous work...
376     if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
377         return funcCleanAmounts[func];
378     }
379
380     if (!func->cleansOwnStack()) {
381         funcCleanAmounts[func] = 0;
382         return funcCleanAmounts[func];
383     }
384
385     InstructionDecoder decoder((const unsigned char*)NULL, 0, func->isrc()->getArch());
386     unsigned char *cur;
387
388     std::set<Height> returnCleanVals;
389
390     Function::const_blocklist returnBlocks = func->returnBlocks();
391     auto rets = returnBlocks.begin();
392     for (; rets != returnBlocks.end(); ++rets) {
393          Block *ret = *rets;
394          cur = (unsigned char *) ret->region()->getPtrToInstruction(ret->lastInsnAddr());
395          Instruction::Ptr insn = decoder.decode(cur);
396
397          entryID what = insn->getOperation().getID();
398          if (what != e_ret_near)
399              continue;
400       
401          int val;
402          std::vector<Operand> ops;
403          insn->getOperands(ops);
404          if (ops.size() == 1) {
405              val = 0;
406          } else {
407              Result imm = ops[1].getValue()->eval();
408              assert(imm.defined);
409              val = (int) imm.val.s16val;
410          }
411          returnCleanVals.insert(Height(val));
412     }
413
414         Height clean = Height::meet(returnCleanVals);
415         if (clean == Height::top) {
416                 // Non-returning or tail-call exits?
417                 clean = Height::bottom;
418         }
419
420     funcCleanAmounts[func] = clean;
421
422     return clean;
423 }
424
425 StackAnalysis::StackAnalysis() :
426    func(NULL), intervals_(NULL), word_size(0) {};
427    
428
429 StackAnalysis::StackAnalysis(Function *f) : func(f),
430                                             intervals_(NULL) {
431    word_size = func->isrc()->getAddressWidth();
432    theStackPtr = Expression::Ptr(new RegisterAST(MachRegister::getStackPointer(func->isrc()->getArch())));
433    thePC = Expression::Ptr(new RegisterAST(MachRegister::getPC(func->isrc()->getArch())));
434 };
435
436 void StackAnalysis::debug() {
437 }
438
439 std::string StackAnalysis::TransferFunc::format() const {
440    std::stringstream ret;
441
442    ret << "[";
443    if (target.isValid())
444       ret << target.name();
445    else
446       ret << "<INVALID>";
447    ret << ":=";
448    if (isBottom()) ret << "<BOTTOM>";
449    else if (isTop()) ret << "<TOP>";
450    else {
451       if (isAlias())
452          ret << from.name();
453       if (isAbs())
454          ret << abs << dec;
455       if (isDelta()) 
456          ret << "+" << delta << dec;
457    }
458    ret << "]";
459    return ret.str();
460 }
461
462 std::string StackAnalysis::SummaryFunc::format() const {
463    stringstream ret;
464    for (TransferSet::const_iterator iter = accumFuncs.begin();
465         iter != accumFuncs.end(); ++iter) {
466       ret << iter->second.format() << endl;
467    }
468    return ret.str();
469 }
470 void StackAnalysis::findDefinedHeights(ParseAPI::Block* b, Address addr, std::vector<std::pair<MachRegister, Height> >& heights)
471 {
472   if (func == NULL) return;
473   
474   if (!intervals_) {
475     // Check annotation
476     func->getAnnotation(intervals_, Stack_Anno);
477   }
478   if (!intervals_) {
479     // Analyze?
480     if (!analyze()) return;
481   }
482   assert(intervals_);
483   for(RegisterState::iterator i = (*intervals_)[b][addr].begin();
484       i != (*intervals_)[b][addr].end();
485       ++i)
486   {
487     if(i->second.isTop())
488     {
489       continue;
490     }
491     stackanalysis_printf("\t\tAdding %s:%s to defined heights at 0x%lx\n",
492                          i->first.name().c_str(),
493                          i->second.format().c_str(),
494                          addr);
495     
496     heights.push_back(*i);
497   }
498 }
499
500 StackAnalysis::Height StackAnalysis::find(Block *b, Address addr, MachRegister reg) {
501
502   Height ret; // Defaults to "top"
503
504   if (func == NULL) return ret;
505   
506   if (!intervals_) {
507     // Check annotation
508     func->getAnnotation(intervals_, Stack_Anno);
509   }
510   if (!intervals_) {
511     // Analyze?
512     if (!analyze()) return Height();
513   }
514   assert(intervals_);
515
516   //(*intervals_)[b].find(addr, state);
517   //  ret = (*intervals_)[b][addr][reg];
518   Intervals::iterator iter = intervals_->find(b);
519   if (iter == intervals_->end()) {
520           // How do we return "you stupid idiot"?
521
522           return Height::bottom;
523   }
524
525   StateIntervals &sintervals = iter->second;
526   if (sintervals.empty()) {
527           return Height::bottom;
528   }
529   //Find the last instruction that is <= addr
530   StateIntervals::iterator i = sintervals.lower_bound(addr);
531   if ((i == sintervals.end() && !sintervals.empty()) || 
532       (i->first != addr && i != sintervals.begin())) {
533       i--;
534   }
535   if (i == sintervals.end()) return Height::bottom;
536
537   ret = i->second[reg];
538
539   if (ret.isTop()) {
540      return Height::bottom;
541   }
542   return ret;
543 }
544
545 StackAnalysis::Height StackAnalysis::findSP(Block *b, Address addr) {
546    return find(b, addr, sp());
547 }
548
549 StackAnalysis::Height StackAnalysis::findFP(Block *b, Address addr) {
550    return find(b, addr, fp());
551 }
552
553 std::ostream &operator<<(std::ostream &os, const Dyninst::StackAnalysis::Height &h) {
554   os << "STACK_SLOT[" << h.format() << "]";
555   return os;
556 }
557
558 ///////////////////
559 // Insn effect fragments
560 ///////////////////
561
562 void StackAnalysis::handlePushPop(Instruction::Ptr insn, int sign, TransferFuncs &xferFuncs) {
563    long delta = 0;
564    Operand arg = insn->getOperand(0);
565    // Why was this here? bernat, 12JAN11
566    if (arg.getValue()->eval().defined) {
567       delta = sign * word_size;
568       stackanalysis_printf("\t\t\t Stack height changed by evaluated push/pop: %lx\n", delta);
569    }
570    else {
571            delta = sign * arg.getValue()->size();
572            //cerr << "Odd case: set delta to " << hex << delta << dec << " for instruction " << insn->format() << endl;
573       stackanalysis_printf("\t\t\t Stack height changed by unevalled push/pop: %lx\n", delta);
574    }
575    //   delta = sign *arg.getValue()->size();
576    xferFuncs.push_back(TransferFunc::deltaFunc(sp(), delta));
577
578    // Let's get whatever was popped (if it was)
579    if (insn->getOperation().getID() == e_pop &&
580        !insn->writesMemory()) {
581       MachRegister reg = sp();
582
583       std::set<RegisterAST::Ptr> written;
584       insn->getWriteSet(written);
585       for (std::set<RegisterAST::Ptr>::iterator iter = written.begin(); 
586            iter != written.end(); ++iter) {
587          if ((*iter)->getID() != sp()) reg = (*iter)->getID();
588       }
589       xferFuncs.push_back(TransferFunc::bottomFunc(reg));
590    }
591 }
592
593 void StackAnalysis::handleReturn(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
594    long delta = 0;
595    std::vector<Operand> operands;
596    insn->getOperands(operands);
597    if (operands.size() == 0) {
598       delta = word_size;
599    }
600    else if (operands.size() == 1) {
601       // Ret immediate
602       Result imm = operands[0].getValue()->eval();
603       if (imm.defined) {
604          delta = word_size + imm.convert<int>();
605       }
606       else {
607          stackanalysis_printf("\t\t\t Stack height changed by return: bottom\n");
608          xferFuncs.push_back(TransferFunc::bottomFunc(sp()));   
609       }
610    }
611    stackanalysis_printf("\t\t\t Stack height changed by return: %lx\n", delta);
612    xferFuncs.push_back(TransferFunc::deltaFunc(sp(), delta));   
613    return;
614 }
615
616 void StackAnalysis::handleAddSub(Instruction::Ptr insn, int sign, TransferFuncs &xferFuncs) {
617    // add reg, mem is ignored
618    // add mem, reg bottoms reg
619    if (insn->writesMemory()) return;
620    if (insn->readsMemory()) {
621       handleDefault(insn, xferFuncs);
622       return;
623    }
624
625    std::set<RegisterAST::Ptr> readSet;
626    insn->getOperand(0).getReadSet(readSet);
627    if (readSet.size() != 1) {
628        fprintf(stderr, "readSet != 1\n");
629        handleDefault(insn, xferFuncs);
630        return;
631    }
632
633    // Add/subtract are op0 += (or -=) op1
634    Operand arg = insn->getOperand(1);
635    Result res = arg.getValue()->eval();
636    if(res.defined) {
637      long delta = 0;
638      // Size is in bytes... 
639      switch(res.size()) {
640      case 1:
641        delta = sign * res.convert<int8_t>();
642        break;
643      case 2:
644        delta = sign * res.convert<int16_t>();
645        break;
646      case 4:
647        delta = sign * res.convert<int32_t>();
648        break;
649      case 8:
650        delta = sign * res.convert<int64_t>(); 
651        break;
652      default:
653        assert(0);
654      }
655      stackanalysis_printf("\t\t\t Stack height changed by evalled add/sub: %lx\n", delta);
656      xferFuncs.push_back(TransferFunc::deltaFunc((*(readSet.begin()))->getID(), delta));
657    }
658    else {
659      handleDefault(insn, xferFuncs);
660    }
661
662    return;
663 }
664
665 void StackAnalysis::handleLEA(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
666    // LEA has a pattern of:
667    // op0: target register
668    // op1: add(source, <const>)
669    // 
670    // Since we don't know what the value in source is, we can't do this a priori. Instead,
671    // TRANSFER FUNCTION!
672    
673    stackanalysis_printf("\t\t\t handleLEA, insn = %s\n", insn->format().c_str());
674
675    std::set<RegisterAST::Ptr> readSet;
676    std::set<RegisterAST::Ptr> writtenSet;
677    insn->getOperand(0).getWriteSet(writtenSet); assert(writtenSet.size() == 1);
678    insn->getOperand(1).getReadSet(readSet); //assert(readSet.size() == 1);
679
680    // conservative...
681    if (readSet.size() != 1) {
682     return handleDefault(insn, xferFuncs); 
683    }
684
685    TransferFunc lea = TransferFunc::aliasFunc((*(readSet.begin()))->getID(), (*(writtenSet.begin()))->getID());
686
687    // LEA also performs computation, so we need to determine and set the delta parameter.
688    // Let's do that the icky way for now
689    insn->getOperand(1).getValue()->bind((*(readSet.begin())).get(), Result(u32, 0));
690    Result res = insn->getOperand(1).getValue()->eval();
691    if (!res.defined) {
692      handleDefault(insn, xferFuncs);
693      return;
694    }
695    long delta = 0;
696    // Size is in bytes... 
697    switch(res.size()) {
698    case 1:
699      delta = (long) res.convert<int8_t>();
700      break;
701    case 2:
702      delta =  (long) res.convert<int16_t>();
703      break;
704    case 4:
705      delta =  (long) res.convert<int32_t>();
706      break;
707    case 8:
708      delta =  (long) res.convert<int64_t>();
709      break;
710    default:
711      assert(0);
712    }
713    lea.delta = delta;
714    xferFuncs.push_back(lea);
715
716    return;
717 }
718
719 void StackAnalysis::handleLeave(TransferFuncs &xferFuncs) {
720    // This is... mov esp, ebp; pop ebp.
721    // Handle it as such.
722
723    // mov esp, ebp;
724     xferFuncs.push_back(TransferFunc::aliasFunc(fp(), sp()));
725     
726    // pop ebp
727     xferFuncs.push_back(TransferFunc::deltaFunc(sp(), word_size)); 
728    xferFuncs.push_back(TransferFunc::bottomFunc(fp()));
729 }
730
731 void StackAnalysis::handlePushPopFlags(int sign, TransferFuncs &xferFuncs) {
732    // Fixed-size push/pop
733    xferFuncs.push_back(TransferFunc::deltaFunc(sp(), sign * word_size));
734 }
735
736 void StackAnalysis::handlePushPopRegs(int sign, TransferFuncs &xferFuncs) {
737    // Fixed-size push/pop
738         // 8 registers
739    xferFuncs.push_back(TransferFunc::deltaFunc(sp(), sign * 8 * word_size));
740 }
741
742 void StackAnalysis::handlePowerAddSub(Instruction::Ptr insn, int sign, TransferFuncs &xferFuncs) {
743    // Add/subtract are op0 = op1 +/- op2; we'd better read the stack pointer as well as writing it
744    if (!insn->isRead(theStackPtr) ||
745        !insn->isWritten(theStackPtr)) {
746       return handleDefault(insn, xferFuncs);
747    }
748    
749    Operand arg = insn->getOperand(2);
750    Result res = arg.getValue()->eval();
751    if(res.defined) {
752       xferFuncs.push_back(TransferFunc::deltaFunc(sp(), sign * res.convert<long>()));
753       stackanalysis_printf("\t\t\t Stack height changed by evalled add/sub: %lx\n", sign * res.convert<long>());
754    }
755    else {
756       xferFuncs.push_back(TransferFunc::bottomFunc(sp()));
757       stackanalysis_printf("\t\t\t Stack height changed by unevalled add/sub: bottom\n");
758    }   
759    return;
760 }
761
762 void StackAnalysis::handlePowerStoreUpdate(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
763    if(!insn->isWritten(theStackPtr)) {
764       return handleDefault(insn, xferFuncs);
765    }
766    
767    std::set<Expression::Ptr> memWriteAddrs;
768    insn->getMemoryWriteOperands(memWriteAddrs);
769    Expression::Ptr stackWrite = *(memWriteAddrs.begin());
770    stackanalysis_printf("\t\t\t ...checking operand %s\n", stackWrite->format().c_str());
771    stackanalysis_printf("\t\t\t ...binding %s to 0\n", theStackPtr->format().c_str());
772    stackWrite->bind(theStackPtr.get(), Result(u32, 0));
773    Result res = stackWrite->eval();
774    if(res.defined) {
775       long delta = res.convert<long>();
776       xferFuncs.push_back(TransferFunc::deltaFunc(sp(), delta));
777       stackanalysis_printf("\t\t\t Stack height changed by evalled stwu: %lx\n", delta);
778    }
779    else {
780       xferFuncs.push_back(TransferFunc::bottomFunc(sp()));
781       stackanalysis_printf("\t\t\t Stack height changed by unevalled stwu: bottom\n");
782    }
783 }
784
785 void StackAnalysis::handleMov(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
786    // A couple of cases:
787    // mov reg, reg
788    // mov mem, reg
789    // mov reg, mem
790    // 
791    // The first is fine, the second bottoms the reg, and the third we ignore.
792
793    if (insn->writesMemory()) return;
794    if (insn->readsMemory()) {
795       handleDefault(insn, xferFuncs);
796       return;
797    }
798    MachRegister read;
799    MachRegister written;
800    std::set<RegisterAST::Ptr> regs;
801    RegisterAST::Ptr reg;
802
803    insn->getWriteSet(regs);
804    if (regs.size() > 1) {
805        handleDefault(insn, xferFuncs);
806        return;
807    }
808
809    assert(regs.size() == 1);
810    reg = *(regs.begin());
811    written = reg->getID();
812    regs.clear();
813
814    insn->getReadSet(regs);
815    if (regs.size() > 1) {
816        //assert(regs.size() < 2);
817        // I had been asserting that there were two registers. Then a rep-prefixed mov instruction came
818        // along and ruined my day...
819        // This is a garbage instruction that is prefixed. Treat as bottom. 
820        handleDefault(insn, xferFuncs);
821        return;
822    }
823
824
825    if (!regs.empty()) {
826            reg = *(regs.begin());
827            read = reg->getID();
828    }
829    regs.clear();
830    
831    if (read.isValid()) {
832            stackanalysis_printf("\t\t\t Alias detected: %s -> %s\n", read.name().c_str(), written.name().c_str());
833            xferFuncs.push_back(TransferFunc::aliasFunc(read, written));
834    }
835    else {
836            xferFuncs.push_back(TransferFunc::bottomFunc(written));
837            stackanalysis_printf("\t\t\t Non-register-register move: %s set to bottom\n", written.name().c_str());
838    }
839 }
840
841 void StackAnalysis::handleZeroExtend(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
842     // This instruction zero extends the read register into the written register
843
844     if (insn->writesMemory()) return;
845     if (insn->readsMemory()) {
846         // Same as handleMov
847         handleDefault(insn, xferFuncs);
848         return;
849     }
850
851     MachRegister read;
852     MachRegister written;
853     std::set<RegisterAST::Ptr> regs;
854     RegisterAST::Ptr reg;
855
856     insn->getWriteSet(regs);
857     if (regs.size() != 1) {
858         handleDefault(insn, xferFuncs);
859         return;
860     }
861     reg = *(regs.begin());
862     written = reg->getID();
863     regs.clear();
864
865     insn->getReadSet(regs);
866     if (regs.size() != 1) {
867         handleDefault(insn, xferFuncs);
868         return;
869     }
870     reg = *(regs.begin());
871     read = reg->getID();
872
873     stackanalysis_printf("\t\t\t Alias detected: %s -> %s\n", read.name().c_str(), written.name().c_str());
874     xferFuncs.push_back(TransferFunc::aliasFunc(read, written));
875 }
876
877 void StackAnalysis::handleSignExtend(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
878     // This instruction sign extends the read register into the written register
879     // Aliasing insn't really correct here...sign extension is going to change the value...
880
881     if (insn->writesMemory()) return;
882     if (insn->readsMemory()) {
883         // Same as handleMov
884         handleDefault(insn, xferFuncs);
885         return;
886     }
887
888     MachRegister read;
889     MachRegister written;
890     std::set<RegisterAST::Ptr> regs;
891     RegisterAST::Ptr reg;
892
893     insn->getWriteSet(regs);
894     if (regs.size() != 1) {
895         handleDefault(insn, xferFuncs);
896         return;
897     }
898     reg = *(regs.begin());
899     written = reg->getID();
900     regs.clear();
901
902     insn->getReadSet(regs);
903     if (regs.size() != 1) {
904         handleDefault(insn, xferFuncs);
905         return;
906     }
907     reg = *(regs.begin());
908     read = reg->getID();
909
910     stackanalysis_printf("\t\t\t Sign extend insn detected: %s -> %s (must be top or bottom)\n", read.name().c_str(), written.name().c_str());
911     xferFuncs.push_back(TransferFunc::aliasFunc(read, written, true));
912     return;
913 }
914
915 void StackAnalysis::handleDefault(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
916    std::set<RegisterAST::Ptr> written;
917    insn->getWriteSet(written);
918    for (std::set<RegisterAST::Ptr>::iterator iter = written.begin(); 
919         iter != written.end(); ++iter) {
920
921       xferFuncs.push_back(TransferFunc::aliasFunc((*iter)->getID(), (*iter)->getID(), true));
922       stackanalysis_printf("\t\t\t Unhandled insn %s detected: %s set to topBottom\n", insn->format().c_str(),
923                            (*iter)->getID().name().c_str());
924    }
925    return;
926 }
927
928 bool StackAnalysis::isCall(Instruction::Ptr insn) {
929    return insn->getCategory() == c_CallInsn;
930 }
931
932 bool StackAnalysis::handleNormalCall(Instruction::Ptr insn, Block *block, Offset off, TransferFuncs &xferFuncs) {
933    if (!insn->getControlFlowTarget()) return false;
934
935    // Must be a thunk based on parsing.
936    if (off != block->lastInsnAddr()) return false;
937    
938    // Bottom callee-written registers
939    ABI* abi = ABI::getABI(word_size);
940    const bitArray callWritten = abi->getCallWrittenRegisters();
941    for (auto iter = abi->getIndexMap()->begin();
942            iter != abi->getIndexMap()->end();
943            ++iter) {
944        // We only care about GPRs right now
945        unsigned int gpr;
946        Architecture arch = insn->getArch();
947        switch(arch) {
948            case Arch_x86:
949                gpr = x86::GPR;
950                break;
951            case Arch_x86_64:
952                gpr = x86_64::GPR;
953                break;
954            case Arch_ppc32:
955                gpr = ppc32::GPR;
956                break;
957            case Arch_ppc64:
958                gpr = ppc64::GPR;
959                break;
960            default:
961                handleDefault(insn, xferFuncs);
962                return true;
963        };
964        if ((*iter).first.regClass() == gpr) {
965            if (callWritten.test((*iter).second)) {
966                xferFuncs.push_back(TransferFunc::bottomFunc((*iter).first));
967            }
968        }
969    }
970
971    const Block::edgelist & outs = block->targets();  
972    Block::edgelist::const_iterator eit = outs.begin();
973    for( ; eit != outs.end(); ++eit) {
974       Edge *cur_edge = (Edge*)*eit;
975       
976       if (cur_edge->type() == DIRECT) {
977          // For some reason we're treating this
978          // call as a branch. So it shifts the stack
979          // like a push (heh) and then we're done.
980          stackanalysis_printf("\t\t\t Stack height changed by simulate-jump call\n");
981          xferFuncs.push_back(TransferFunc::deltaFunc(sp(), -1 * word_size));
982          return true;
983       }
984       
985       if (cur_edge->type() != CALL) 
986          continue;
987       
988       Block *target_bbl = cur_edge->trg();
989       Function *target_func = target_bbl->obj()->findFuncByEntry(target_bbl->region(), target_bbl->start());
990       
991       if (!target_func)
992          continue;
993       
994       Height h = getStackCleanAmount(target_func);
995       if (h == Height::bottom) {
996          stackanalysis_printf("\t\t\t Stack height changed by self-cleaning function: bottom\n");
997          xferFuncs.push_back(TransferFunc::bottomFunc(sp()));
998       }
999       else {
1000          stackanalysis_printf("\t\t\t Stack height changed by self-cleaning function: %ld\n", h.height());
1001          xferFuncs.push_back(TransferFunc::deltaFunc(sp(), h.height()));
1002       }
1003       return true;
1004
1005    }
1006    stackanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
1007    return true;
1008 }
1009                                        
1010
1011 bool StackAnalysis::handleThunkCall(Instruction::Ptr insn, TransferFuncs &xferFuncs) {
1012    // We know that we're not a normal call, so it depends on whether
1013    // the CFT is "next instruction" or not. 
1014    if (insn->getCategory() != c_CallInsn ||
1015        !insn->getControlFlowTarget()) return false;
1016    
1017    // Eval of getCFT(0) == size?
1018    Expression::Ptr cft = insn->getControlFlowTarget();
1019    cft->bind(thePC.get(), Result(u32, 0));
1020    Result res = cft->eval();
1021    if (!res.defined) return false;
1022    if (res.convert<unsigned>() == insn->size()) {
1023       xferFuncs.push_back(TransferFunc::deltaFunc(sp(), -1 * word_size));
1024       return true;
1025    }
1026    // Else we're calling a mov, ret thunk that has no effect on the stack pointer
1027    return true;
1028 }
1029
1030
1031 void StackAnalysis::createEntryInput(RegisterState &input) {
1032    // FIXME for POWER/non-IA32
1033    // IA32 - the in height includes the return address and therefore
1034    // is <wordsize>
1035    // POWER - the in height is 0
1036
1037 #if defined(arch_power)
1038    input[sp()] = Height(0);
1039 #elif (defined(arch_x86) || defined(arch_x86_64))
1040    input[sp()] = Height(-1 * word_size);
1041 #else
1042    assert(0 && "Unimplemented architecture");
1043 #endif
1044 }
1045
1046 StackAnalysis::RegisterState StackAnalysis::getSrcOutputRegs(Edge* e)
1047 {
1048         Block* b = e->src();
1049         return blockOutputs[b];
1050 }
1051
1052 void StackAnalysis::meetInputs(Block *block, RegisterState& blockInput, RegisterState &input) {
1053    input.clear();
1054
1055    //Intraproc epred; // ignore calls, returns in edge iteration
1056    //NoSinkPredicate epred2(&epred); // ignore sink node (unresolvable)
1057    intra_nosink epred2;
1058    
1059    const Block::edgelist & inEdges = block->sources();
1060    std::for_each(boost::make_filter_iterator(epred2, inEdges.begin(), inEdges.end()),
1061                  boost::make_filter_iterator(epred2, inEdges.end(), inEdges.end()),
1062                  boost::bind(&StackAnalysis::meet,
1063                                          this,
1064                                          boost::bind(&StackAnalysis::getSrcOutputRegs, this, _1),
1065                                          boost::ref(input)));
1066
1067    meet(blockInput, input);
1068
1069 }
1070
1071 void StackAnalysis::meet(const RegisterState &input, RegisterState &accum) {
1072    for (RegisterState::const_iterator iter = input.begin();
1073         iter != input.end(); ++iter) {
1074       accum[iter->first] = Height::meet(iter->second, accum[iter->first]);
1075    }
1076 }
1077
1078 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::deltaFunc(MachRegister r, long d) {
1079    return TransferFunc(uninitialized, d, MachRegister(), r);
1080 }
1081
1082 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::absFunc(MachRegister r, long a, bool i) {
1083    return TransferFunc(a, 0, MachRegister(), r, i);
1084 }
1085
1086 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::aliasFunc(MachRegister f, MachRegister t, bool i) {
1087    return TransferFunc (uninitialized, 0, f, t, i);
1088 }
1089
1090 StackAnalysis::TransferFunc StackAnalysis::TransferFunc::bottomFunc(MachRegister r) {
1091    return TransferFunc(notUnique, notUnique, MachRegister(), r);
1092 }
1093
1094 bool StackAnalysis::TransferFunc::isBottom() const {
1095    return (delta == notUnique || abs == notUnique);
1096 }
1097
1098 bool StackAnalysis::TransferFunc::isTop() const {
1099    return (!isDelta() && !isAbs() && !isAlias());
1100 }
1101
1102 bool StackAnalysis::TransferFunc::isAlias() const {
1103    return from.isValid();
1104 }
1105
1106 bool StackAnalysis::TransferFunc::isAbs() const {
1107    return (abs != uninitialized);
1108 }
1109
1110 bool StackAnalysis::TransferFunc::isDelta() const {
1111    return (delta != 0);
1112 }
1113
1114 bool StackAnalysis::TransferFunc::isTopBottom() const {
1115     return topBottom;
1116 }
1117
1118 // Destructive update of the input map. Assumes inputs are absolute, uninitalized, or 
1119 // bottom; no deltas.
1120 StackAnalysis::Height StackAnalysis::TransferFunc::apply(const RegisterState &inputs ) const {
1121         assert(target.isValid());
1122         // Bottom stomps everything
1123         if (isBottom()) {
1124                 return Height::bottom;
1125         }
1126
1127         RegisterState::const_iterator iter = inputs.find(target);
1128         Height input;
1129         if (iter != inputs.end()) {
1130                 input = iter->second;
1131         }
1132         else {
1133                 input = Height::top;
1134         }
1135
1136     bool isTopBottomOrig = isTopBottom();
1137
1138    if (isAbs()) {
1139       // We cannot be an alias, as the absolute removes that. 
1140       assert(!isAlias());
1141       // Apply the absolute
1142       // NOTE: an absolute is not a stack height, set input to top
1143       //input = abs;
1144       input = Height::top;
1145    }
1146    if (isAlias()) {
1147       // Cannot be absolute
1148       assert(!isAbs());
1149       // Copy the input value from whatever we're an alias of.
1150           RegisterState::const_iterator iter2 = inputs.find(from);
1151           if (iter2 != inputs.end()) input = iter2->second;
1152           else input = Height::top;
1153    }
1154    if (isDelta()) {
1155       input += delta;
1156    }
1157    if (isTopBottomOrig) {
1158        if (!input.isTop()) {
1159            input = Height::bottom;
1160        }
1161    }
1162    return input;
1163 }
1164
1165 // Accumulation to the input map. This is intended to create a summary, so we create
1166 // something that can take further input.
1167 void StackAnalysis::TransferFunc::accumulate(std::map<MachRegister, TransferFunc> &inputs ) {
1168    TransferFunc &input = inputs[target];
1169    if (input.target.isValid()) assert(input.target == target);
1170    input.target = target; // Default constructed TransferFuncs won't have this
1171    assert(target.isValid());
1172
1173    // Bottom stomps everything
1174    if (isBottom()) {
1175       input = bottomFunc(target);
1176       return;
1177    }
1178    bool isTopBottomOrig = isTopBottom();
1179    if (!input.isTopBottom()) {
1180        input.topBottom = isTopBottomOrig;
1181    }
1182    // Absolutes override everything else
1183    if (isAbs()) {
1184       input = absFunc(target, abs, isTopBottomOrig);
1185       return;
1186    }
1187    // Aliases can be tricky
1188    if (isAlias()) {
1189       // We need to record that we want to take the inflow height
1190       // of a different register. 
1191            // Don't do an inputs[from] as that creates
1192            std::map<MachRegister, TransferFunc>::iterator iter = inputs.find(from);
1193            if (iter == inputs.end()) {
1194                    // Aliasing to something we haven't seen yet; easy
1195                    input = *this;
1196            input.topBottom = isTopBottomOrig;
1197                    return;
1198            }
1199
1200            TransferFunc &alias = iter->second;
1201       
1202       if (alias.isAbs()) {
1203          // Easy; we reset the height, so we don't care about the inflow height.
1204          // This might be a delta from that absolute, but all that we care about is that
1205          // we ignore any inflow. 
1206          assert(!alias.isAlias());
1207                  input = absFunc(input.target, alias.abs);
1208          input.topBottom = isTopBottomOrig || alias.isTopBottom(); // If we got an abs from an isTopBottom, this also needs to be set
1209                  assert(input.target.isValid());
1210
1211          // if the input was also a delta, apply this
1212          if (isDelta()) {
1213             input.delta += delta;
1214          }
1215          return;
1216       }
1217       if (alias.isAlias()) {
1218          // Transitivity! We cut that short.
1219          // Again, it might be a delta since the alias, which we'll copy over. It cannot
1220          // be an absolute because that will remove the alias (and vice versa).
1221          assert(!alias.isAbs());
1222          input = alias;
1223          input.target = target;
1224          input.topBottom = isTopBottomOrig || alias.isTopBottom();
1225          assert(input.target.isValid());
1226                    
1227                  // if the input was also a delta, apply this also 
1228                  if (isDelta()) {
1229                     input.delta += delta;
1230                  }
1231       
1232          return;
1233       }
1234
1235           // Default case: record the alias, zero out everything else, copy over the delta
1236           // if it's defined.
1237           //input.target is defined
1238           input.from = alias.target;
1239           input.abs = uninitialized;
1240           if (alias.isDelta()) {
1241          input.delta = alias.delta;
1242           }
1243           else {
1244                   input.delta = 0;
1245           }
1246       input.topBottom = isTopBottomOrig;
1247
1248           // if the input was also a delta, apply this also 
1249           if (isDelta()) {
1250             input.delta += delta;
1251           }
1252
1253           return;
1254    }
1255    if (isDelta()) {
1256       // A delta can apply cleanly to anything, since Height += handles top/bottom
1257       input.delta += delta;
1258       return;
1259    }
1260    // Reachable because isDelta returns false for delta = 0; this is OK
1261    return;
1262 }
1263
1264 void StackAnalysis::SummaryFunc::apply(const RegisterState &in, RegisterState &out) const {
1265         // Copy all the elements we don't have xfer funcs for. 
1266         out = in;
1267
1268         // We apply in parallel, since all summary funcs are from the start of the block.
1269         for (TransferSet::const_iterator iter = accumFuncs.begin();
1270                 iter != accumFuncs.end(); ++iter) {
1271                 assert(iter->first.isValid());
1272                 out[iter->first] = iter->second.apply(in);
1273         }
1274 }
1275
1276
1277 void StackAnalysis::SummaryFunc::add(TransferFuncs &xferFuncs) {
1278    // We need to update our register->xferFunc map
1279    // with the effects of each of the transferFuncs. 
1280    
1281    for (TransferFuncs::iterator iter = xferFuncs.begin(); 
1282         iter != xferFuncs.end(); ++iter) {
1283       TransferFunc &func = *iter;
1284
1285       func.accumulate(accumFuncs);
1286       validate();
1287    }
1288
1289 }
1290
1291 void StackAnalysis::SummaryFunc::validate() const {
1292    for (TransferSet::const_iterator iter = accumFuncs.begin(); 
1293            iter != accumFuncs.end(); ++iter)
1294    {
1295            const TransferFunc &func = iter->second;
1296            assert(func.target.isValid());
1297            if (func.isAlias()) assert(!func.isAbs());
1298            if (func.isAbs()) assert(!func.isAlias());
1299            if (func.isBottom()) assert(!func.isAlias());
1300    }
1301 }
1302
1303 MachRegister StackAnalysis::sp() { 
1304  return MachRegister::getStackPointer(func->isrc()->getArch());
1305 }
1306
1307 MachRegister StackAnalysis::fp() { 
1308  return MachRegister::getFramePointer(func->isrc()->getArch());
1309 }
1310
1311 std::string StackAnalysis::format(const RegisterState &input) const {
1312         std::stringstream ret;
1313         for (RegisterState::const_iterator iter = input.begin(); iter != input.end(); ++iter) {
1314                 ret << iter->first.name() << " := " << iter->second.format() << ", ";
1315         }
1316         return ret.str();
1317 }