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