Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / IA_IAPI.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include "IA_IAPI.h"
33
34 #include "Register.h"
35 #include "Dereference.h"
36 #include "Immediate.h"
37 #include "BinaryFunction.h"
38 #include "debug.h"
39 #include "symtab.h"
40
41
42 #include <deque>
43 #if defined(arch_x86) || defined(arch_x86_64)
44 #include "RegisterIDs-x86.h"
45 #endif
46
47 using namespace Dyninst;
48 using namespace InstructionAPI;
49
50
51 IA_IAPI::IA_IAPI(InstructionDecoder dec_, Address where_,
52                 image_func* f)
53     : InstructionAdapter(where_, f), dec(dec_),
54     validCFT(false), cachedCFT(0)
55 {
56     hascftstatus.first = false;
57     tailCall.first = false;
58     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
59 }
60
61 IA_IAPI::IA_IAPI(InstructionDecoder dec_, Address where_,
62                 image * im)
63     : InstructionAdapter(where_, im), dec(dec_),
64     validCFT(false), cachedCFT(0)
65 {
66     hascftstatus.first = false;
67     tailCall.first = false;
68     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
69 }
70
71 void IA_IAPI::advance()
72 {
73     if(!curInsn()) {
74         parsing_printf("..... WARNING: failed to advance InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
75                        allInsns.size());
76         return;
77     }
78     InstructionAdapter::advance();
79     current += curInsn()->size();
80     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
81     if(!curInsn())
82     {
83         parsing_printf("......WARNING: after advance at 0x%lx, curInsn() NULL\n", current);
84     }
85     validCFT = false;
86     hascftstatus.first = false;
87     tailCall.first = false;
88 }
89
90 size_t IA_IAPI::getSize() const
91 {
92     assert(curInsn());
93     return curInsn()->size();
94 }
95
96 bool IA_IAPI::hasCFT() const
97 {
98     if(hascftstatus.first) return hascftstatus.second;
99     InsnCategory c = curInsn()->getCategory();
100     hascftstatus.second = false;
101     if(c == c_BranchInsn ||
102        c == c_ReturnInsn)
103     {
104         hascftstatus.second = true;
105     }
106     if(c == c_CallInsn)
107     {
108         if(isRealCall()) {
109             hascftstatus.second = true;
110         }
111         if(isDynamicCall()) {
112             hascftstatus.second = true;
113         }
114         if(simulateJump()) {
115             hascftstatus.second = true;
116         }
117     }
118     return hascftstatus.second;
119 }
120
121 bool IA_IAPI::isAbortOrInvalidInsn() const
122 {
123     entryID e = curInsn()->getOperation().getID();
124     if(e == e_No_Entry)
125     {
126         parsing_printf("...WARNING: un-decoded instruction at 0x%x\n", current);
127     }
128     return e == e_No_Entry ||
129             e == e_int3 ||
130             e == e_hlt;
131 }
132
133 bool IA_IAPI::isAllocInsn() const
134 {
135 #if !defined(arch_ia64)
136     // IA64 only
137     return false;
138 #else
139     assert(!"Implement for IA64\n");
140     return false;
141 #endif
142 }
143
144 bool IA_IAPI::isFrameSetupInsn(Instruction::Ptr i) const
145 {
146     if(i->getOperation().getID() == e_mov)
147     {
148         static RegisterAST::Ptr ebp(new RegisterAST(r_EBP));
149         static RegisterAST::Ptr esp(new RegisterAST(r_ESP));
150         static RegisterAST::Ptr rbp(new RegisterAST(r_RBP));
151         static RegisterAST::Ptr rsp(new RegisterAST(r_RSP));
152         if((i->isRead(rsp) ||
153             i->isRead(esp)) &&
154             (i->isWritten(rbp) ||
155             i->isWritten(ebp)))
156         {
157             return true;
158         }
159     }
160     return false;
161 }
162
163 bool IA_IAPI::isFrameSetupInsn() const
164 {
165     return isFrameSetupInsn(curInsn());
166 }
167
168 bool IA_IAPI::isNop() const
169 {
170     // TODO: add LEA no-ops
171     assert(curInsn());
172     if(curInsn()->getOperation().getID() == e_nop)
173         return true;
174     if(curInsn()->getOperation().getID() == e_lea)
175     {
176         std::set<Expression::Ptr> memReadAddr;
177         curInsn()->getMemoryReadOperands(memReadAddr);
178         std::set<RegisterAST::Ptr> writtenRegs;
179         curInsn()->getWriteSet(writtenRegs);
180         
181         if(memReadAddr.size() == 1 && writtenRegs.size() == 1)
182         {
183             if(**(memReadAddr.begin()) == **(writtenRegs.begin()))
184             {
185                 return true;
186             }
187             // TODO: check for zero displacement--do we want to bind here?
188         }
189     }
190     return false;
191 }
192
193 bool IA_IAPI::isDynamicCall() const
194 {
195     if(curInsn() && (curInsn()->getCategory() == c_CallInsn))
196     {
197         if(getCFT() == 0)
198         {
199             parsing_printf("... Call 0x%lx is indirect\n", current);
200             return true;
201         }
202     }
203     return false;
204 }
205
206 bool IA_IAPI::isAbsoluteCall() const
207 {
208     if(curInsn()->getCategory() == c_CallInsn)
209     {
210         Expression::Ptr cft = curInsn()->getControlFlowTarget();
211         if(cft && dyn_detail::boost::dynamic_pointer_cast<Immediate>(cft))
212         {
213             return true;
214         }
215     }
216     return false;
217 }
218
219
220 bool IA_IAPI::isReturn() const
221 {
222     return curInsn()->getCategory() == c_ReturnInsn;
223 }
224 bool IA_IAPI::isBranch() const
225 {
226     return curInsn()->getCategory() == c_BranchInsn;
227 }
228 bool IA_IAPI::isCall() const
229 {
230     return curInsn()->getCategory() == c_CallInsn;
231 }
232
233 bool IA_IAPI::isInterruptOrSyscall() const
234 {
235     return ((curInsn()->getOperation().getID() == e_int) ||
236             (curInsn()->getOperation().getID() == e_int3) ||
237             (curInsn()->getOperation().getID() == e_syscall));
238 }
239
240
241
242 void IA_IAPI::getNewEdges(
243         std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges,
244         image_basicBlock* currBlk,
245         unsigned int num_insns,
246         dictionary_hash<Address,
247         std::string> *pltFuncs) const
248 {
249     if(!context) {
250         fprintf(stderr, "[%s] getNewEdges not supported in non-image_func"
251                         "context\n", FILE__);
252         return;
253     }
254
255     // Only call this on control flow instructions!
256     if(curInsn()->getCategory() == c_CallInsn)
257     {
258         Address target = getCFT();
259         if(isRealCall())
260         {
261             outEdges.push_back(std::make_pair(target, ET_NOEDGE));
262         }
263         else
264         {
265             if(img->isValidAddress(getCFT()))
266             {
267                 if(simulateJump())
268                 {
269                     parsing_printf("[%s:%u] call at 0x%lx simulated as "
270                             "jump to 0x%lx\n",
271                     FILE__,__LINE__,getAddr(),getCFT());
272                     outEdges.push_back(std::make_pair(target, ET_DIRECT));
273                     return;
274                 }
275             }
276         }
277         outEdges.push_back(std::make_pair(getAddr() + getSize(),
278                            ET_FUNLINK));
279         return;
280     }
281     else if(curInsn()->getCategory() == c_BranchInsn)
282     {
283         if(curInsn()->allowsFallThrough())
284         {
285             outEdges.push_back(std::make_pair(getCFT(),
286                                ET_COND_TAKEN));
287             outEdges.push_back(std::make_pair(getNextAddr(), ET_COND_NOT_TAKEN));
288             return;
289         }
290         // Direct jump
291         else if(getCFT() != 0)
292         {
293             Address catchStart;
294             if(context->archProcExceptionBlock(catchStart, getNextAddr()))
295             {
296                 outEdges.push_back(std::make_pair(catchStart, ET_CATCH));
297             }
298         
299
300             if(!isTailCall(num_insns))
301             {
302                 if(!(*pltFuncs).defines(getCFT()))
303                 {
304                     outEdges.push_back(std::make_pair(getCFT(),
305                                        ET_DIRECT));
306                 }
307                 else
308                 {
309                     parsing_printf("%s[%d]: PLT tail call to %x\n", FILE__, __LINE__, getCFT());
310                     outEdges.push_back(std::make_pair(getCFT(), ET_NOEDGE));
311                     tailCall.second = true;
312                 }
313             }
314             else
315             {
316                 parsing_printf("%s[%d]: tail call to %x\n", FILE__, __LINE__, getCFT());
317                 outEdges.push_back(std::make_pair(getCFT(), ET_NOEDGE));
318             }
319             return;
320         }
321         else
322         {
323             parsing_printf("... indirect jump at 0x%x\n", current);
324             if( num_insns == 2 ) {
325                 parsing_printf("... uninstrumentable due to 0 size\n");
326                 return;
327             }
328             if(isTailCall(num_insns)) {
329                 parsing_printf("%s[%d]: indirect tail call %s at 0x%lx\n", FILE__, __LINE__,
330                                curInsn()->format().c_str(), current);
331                 return;
332             }
333             parsedJumpTable = true;
334             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
335             return;
336         }
337     }
338     else if(curInsn()->getCategory() == c_ReturnInsn)
339     {
340         if(curInsn()->allowsFallThrough())
341         {
342             outEdges.push_back(std::make_pair(getNextAddr(), ET_FALLTHROUGH));
343             return;
344         }
345         return;
346     }
347     fprintf(stderr, "Unhandled instruction %s\n", curInsn()->format().c_str());
348     assert(0);
349 }
350
351 bool IA_IAPI::isMovAPSTable(std::vector<std::pair< Address, EdgeTypeEnum > >& outEdges) const
352 {
353     /**
354     * AMD-64 gcc emits a re-accuring idiom of:
355      *         jmpq   *%r8
356      *         movaps %xmm7,-0xf(%rax)
357      *         movaps %xmm6,-0x1f(%rax)
358      *         movaps %xmm5,-0x2f(%rax)
359      *         movaps %xmm4,-0x3f(%rax)
360      *         movaps %xmm3,-0x4f(%rax)
361      *         movaps %xmm2,-0x5f(%rax)
362      *         movaps %xmm1,-0x6f(%rax)
363      *         movaps %xmm0,-0x7f(%rax)
364      *         <other>
365      *
366      * The jump register is calculated in such a way that it'll be difficult
367      * for our analysis to figure it out.  Instead we'll recognize the pattern
368      * of the 'movaps'.  Note that the following instruction is also a valid jump
369      * target
370      **/
371     parsing_printf("\tChecking for movaps table at 0x%lx...\n", current);
372     std::set<Address> found;
373     InstructionDecoder d((const unsigned char*)(img->getPtrToInstruction(current)),
374                           (img->imageOffset() + img->imageLength()) - current);
375     d.setMode(img->getAddressWidth() == 8);
376     Address cur = current;
377     unsigned last_insn_size = 0;
378     InstructionAPI::Instruction::Ptr i = d.decode();
379     cur += i->size();
380     for (;;) {
381         InstructionAPI::Instruction::Ptr insn = d.decode();
382         //All insns in sequence are movaps
383         parsing_printf("\t\tChecking instruction %s\n", insn->format().c_str());
384         if (insn->getOperation().getID() != e_movapd &&
385             insn->getOperation().getID() != e_movaps)
386         {
387             break;
388         }
389         //All insns are same size
390         if (last_insn_size == 0)
391             last_insn_size = insn->size();
392         else if (last_insn_size != insn->size())
393             break;
394
395         found.insert(cur);
396
397         cur += insn->size();
398     }
399     if (found.size() == 8) {
400         found.insert(cur);
401         //It's a match
402         for (std::set<Address>::iterator i=found.begin(); i != found.end(); i++) {
403             outEdges.push_back(std::make_pair(*i, ET_INDIR));
404         }
405         parsing_printf("\tfound\n");
406         return true;
407     }
408     parsing_printf("\tnot found (%d insns)\n", found.size());
409     return false;
410 }
411
412 bool IA_IAPI::isIPRelativeBranch() const
413 {
414             // These don't exist on IA32...
415 #if !defined(arch_x86_64)
416     return false;
417 #endif
418     if(curInsn()->getCategory() == c_BranchInsn &&
419         !getCFT())
420 {
421     static RegisterAST::Ptr thePC(new RegisterAST(RegisterAST::makePC()));
422     static RegisterAST::Ptr rip(new RegisterAST(r_RIP));
423     if(curInsn()->getControlFlowTarget()->isUsed(thePC) ||
424        curInsn()->getControlFlowTarget()->isUsed(rip))
425     {
426         parsing_printf("\tIP-relative indirect jump at 0x%lx\n", current);
427         return true;
428     }
429 }
430     return false;
431     
432 }
433
434 bool IA_IAPI::isTableInsn(Instruction::Ptr i) const
435 {
436     if(i->getOperation().getID() == e_mov && i->readsMemory() && !i->writesMemory())
437     {
438         return true;
439     }
440     if(i->getOperation().getID() == e_lea)
441     {
442         return true;
443     }
444     return false;
445 }
446         
447 std::map<Address, Instruction::Ptr>::const_iterator IA_IAPI::findTableInsn() const
448 {
449     // Check whether the jump is our table insn!
450     Expression::Ptr cft = curInsn()->getControlFlowTarget();
451     if(cft)
452     {
453             std::vector<InstructionAST::Ptr> tmp;
454             cft->getChildren(tmp);
455             if(tmp.size() == 1)
456             {
457                     Expression::Ptr cftAddr = dyn_detail::boost::dynamic_pointer_cast<Expression>(tmp[0]);
458                     parsing_printf("\tChecking indirect jump %s for table insn\n", curInsn()->format().c_str());
459                     static RegisterAST* allGPRs = new RegisterAST(r_ALLGPRS);
460                     cftAddr->bind(allGPRs, Result(u32, 0));
461
462                     Result base = cftAddr->eval();
463                     if(base.defined && base.convert<Address>())
464                     {
465                             parsing_printf("\tAddress in jump\n");
466                             return allInsns.find(current);
467                     }
468             }
469     }
470     std::map<Address, Instruction::Ptr>::const_iterator c =
471         allInsns.find(current);
472     while(!isTableInsn(c->second) && c != allInsns.begin())
473     {
474         --c;
475     }
476     if(isTableInsn(c->second))
477     {
478         return c;
479     }
480     return allInsns.end();
481 }
482         
483 // This should only be called on a known indirect branch...
484 bool IA_IAPI::parseJumpTable(image_basicBlock* currBlk,
485                              std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges) const
486 {
487     if(isIPRelativeBranch())
488     {
489         return false;
490     }
491     std::vector<image_edge*> sourceEdges;
492     currBlk->getSources(sourceEdges);
493     if(sourceEdges.empty())
494     {
495         return false;
496     }
497     if(isMovAPSTable(outEdges))
498     {
499         return true;
500     }
501     bool foundJCCAlongTaken = false;
502     Instruction::Ptr tableInsn;
503     Address tableInsnAddr;
504     std::map<Address, Instruction::Ptr>::const_iterator tableLoc = findTableInsn();
505     if(tableLoc == allInsns.end())
506     {
507         parsing_printf("\tunable to find table insn\n");
508         return false;
509     }
510     tableInsnAddr = tableLoc->first;
511     tableInsn = tableLoc->second;
512     Instruction::Ptr maxSwitchInsn, branchInsn;
513     boost::tie(maxSwitchInsn, branchInsn, foundJCCAlongTaken) = findMaxSwitchInsn(currBlk);
514     if(!maxSwitchInsn || !branchInsn)
515     {
516         parsing_printf("\tunable to fix max switch size\n");
517         return false;
518     }
519     Address thunkOffset;
520     Address thunkInsnAddr;
521     boost::tie(thunkInsnAddr, thunkOffset) = findThunkAndOffset(currBlk);
522     if(thunkInsnAddr != 0)
523     {
524         std::map<Address, Instruction::Ptr>::const_iterator thunkLoc =
525                 allInsns.find(thunkInsnAddr);
526         if(thunkLoc != allInsns.end())
527         {
528             tableLoc = thunkLoc;
529             tableInsnAddr = thunkInsnAddr;
530             tableInsn = thunkLoc->second;
531         }
532     }
533     parsing_printf("\ttableInsn %s at 0x%lx\n",tableInsn->format().c_str(), tableInsnAddr);
534     if(thunkOffset) {
535         parsing_printf("\tThunk-calculated table base address: 0x%lx\n",
536                        thunkOffset);
537     }
538     unsigned tableSize = 0, tableStride = 0;
539     bool ok = computeTableBounds(maxSwitchInsn, branchInsn, tableInsn, foundJCCAlongTaken,
540                                  tableSize, tableStride);
541     if(!ok)
542     {
543         return false;
544     }
545     std::map<Address, Instruction::Ptr>::const_iterator cur = allInsns.find(current);
546     
547     while(tableLoc != cur)
548     {
549         tableLoc++;
550         if(tableLoc->second->getOperation().getID() == e_lea)
551         {
552             parsing_printf("\tchecking instruction %s at 0x%lx for IP-relative LEA\n", tableLoc->second->format().c_str(),
553                            tableLoc->first);
554             Expression::Ptr IPRelAddr = tableLoc->second->getOperand(1).getValue();
555             static RegisterAST* eip(new RegisterAST(r_EIP));
556             static RegisterAST* rip(new RegisterAST(r_RIP));
557             IPRelAddr->bind(eip, Result(s64, tableLoc->first + tableLoc->second->size()));
558             IPRelAddr->bind(rip, Result(s64, tableLoc->first + tableLoc->second->size()));
559             Result iprel = IPRelAddr->eval();
560             if(iprel.defined)
561             {
562                 parsing_printf("\trevising tableInsn to %s at 0x%lx\n",tableLoc->second->format().c_str(), tableLoc->first);
563                 tableInsn = tableLoc->second;
564             }
565
566         }
567         else
568         {
569             parsing_printf("\tChecking for sign-extending mov at 0x%lx...\n", tableLoc->first);
570             if(tableLoc->second->getOperation().getID() == e_movsxd ||
571                tableLoc->second->getOperation().getID() == e_movsx)
572             {
573                 std::set<Expression::Ptr> movsxReadAddr;
574                 tableLoc->second->getMemoryReadOperands(movsxReadAddr);
575                 static Immediate::Ptr four(new Immediate(Result(u8, 4)));
576                 static Expression::Ptr dummy4(new DummyExpr());
577                 static Expression::Ptr dummy2(new DummyExpr());
578                 static Immediate::Ptr two(new Immediate(Result(u8, 2)));
579                 static BinaryFunction::funcT::Ptr multiplier(new BinaryFunction::multResult());
580                 static BinaryFunction::Ptr scaleCheck4(new BinaryFunction(four, dummy4, (tableStride == 8) ? u64: u32,
581                     multiplier));
582                 static BinaryFunction::Ptr scaleCheck2(new BinaryFunction(two, dummy2, (tableStride == 8) ? u64: u32,
583                     multiplier));
584                 for(std::set<Expression::Ptr>::const_iterator readExp =
585                     movsxReadAddr.begin();
586                     readExp != movsxReadAddr.end();
587                     ++readExp)
588                 {
589                     if((*readExp)->isUsed(scaleCheck4))
590                     {
591                         parsing_printf("\tFound sign-extending mov, revising table stride to scale (4)\n");
592                         tableStride = 4;
593                     }
594                     else if((*readExp)->isUsed(scaleCheck2))
595                     {
596                         parsing_printf("\tFound sign-extending mov, revising table stride to scale (2)\n");
597                         tableStride = 2;
598                     }
599                     else
600                     {
601                         parsing_printf("\tFound sign-extending mov insn %s, readExp %s\n",
602                                        tableLoc->second->format().c_str(), (*readExp)->format().c_str());
603                         parsing_printf("\tcouldn't match stride expression %s or %s--HELP!\n",
604                                        scaleCheck2->format().c_str(), scaleCheck4->format().c_str());
605                     }
606                 }
607                 break;
608             }
609         }
610     }
611     Address tableBase = getTableAddress(tableInsn, thunkOffset);
612     return fillTableEntries(thunkOffset, tableBase,
613                             tableSize, tableStride, outEdges);
614 }
615 namespace detail
616 {
617     bool isNonCallEdge(image_edge* e)
618     {
619         return e->getType() != ET_CALL;
620     }
621     bool leadsToVisitedBlock(image_edge* e, const std::set<image_basicBlock*>& visited)
622     {
623         image_basicBlock* src = e->getSource();
624         return visited.find(src) != visited.end();
625     }
626 };
627
628
629 Address IA_IAPI::findThunkInBlock(image_basicBlock* curBlock, Address& thunkOffset) const
630 {
631     const unsigned char* buf =
632             (const unsigned char*)(img->getPtrToInstruction(curBlock->firstInsnOffset()));
633     
634     InstructionDecoder dec(buf, curBlock->getSize() + 16);
635     dec.setMode(img->getAddressWidth() == 8);
636     IA_IAPI * blockptr = NULL;
637     if(context) 
638         blockptr = new IA_IAPI(dec,curBlock->firstInsnOffset(),context);
639     else
640         blockptr = new IA_IAPI(dec,curBlock->firstInsnOffset(),img);
641     IA_IAPI & block = *blockptr;
642
643     parsing_printf("\tchecking block at 0x%lx for thunk\n", curBlock->firstInsnOffset());
644     while(block.getAddr() < curBlock->endOffset())
645     {
646         if(block.getInstruction()->getCategory() == c_CallInsn)
647         {
648             parsing_printf("\tchecking call at 0x%lx for thunk\n", block.getAddr());
649             if(!block.isRealCall())
650             {
651                 parsing_printf("\tthunk found at 0x%lx, checking for add\n", block.getAddr());
652                 block.advance();
653                 thunkOffset = block.getAddr();
654                 Instruction::Ptr addInsn = block.getInstruction();
655                 if(addInsn)
656                     parsing_printf("\tinsn after thunk: %s\n", addInsn->format().c_str());
657                 else
658                     parsing_printf("\tNO INSN after thunk at 0x%lx\n", thunkOffset);
659                 if(addInsn && (addInsn->getOperation().getID() == e_add))
660                 {
661                     Result imm = addInsn->getOperand(1).getValue()->eval();
662                     Result imm2 = addInsn->getOperand(0).getValue()->eval();
663                     if(imm.defined)
664                     {
665                         Address thunkDiff = imm.convert<Address>();
666                         parsing_printf("\tsetting thunkOffset to 0x%lx (0x%lx + 0x%lx)\n",
667                                     thunkOffset+thunkDiff, thunkOffset, thunkDiff);
668                         Address ret = block.getPrevAddr();
669                         thunkOffset = thunkOffset + thunkDiff;
670                         delete blockptr;
671                         return ret;
672                     }
673                     else if(imm2.defined)
674                     {
675                         Address thunkDiff = imm2.convert<Address>();
676                         parsing_printf("\tsetting thunkOffset to 0x%lx (0x%lx + 0x%lx)\n",
677                                     thunkOffset+thunkDiff, thunkOffset, thunkDiff);
678                         Address ret = block.getPrevAddr();
679                         thunkOffset = thunkOffset + thunkDiff;
680                         delete blockptr;
681                         return ret;
682                     }
683                     else
684                     {
685                         parsing_printf("\tadd insn %s found following thunk at 0x%lx, couldn't bind operands!\n",
686                                     addInsn->format().c_str(), thunkOffset);
687                     }
688                 }
689                 thunkOffset = 0;
690             }
691         }
692         else if(block.getInstruction()->getOperation().getID() == e_lea)
693             // Look for an AMD64 IP-relative LEA.  If we find one, it should point to the start of a
694         {    // relative jump table.
695             parsing_printf("\tchecking instruction %s at 0x%lx for IP-relative LEA\n", block.getInstruction()->format().c_str(),
696                            block.getAddr());
697             Expression::Ptr IPRelAddr = block.getInstruction()->getOperand(1).getValue();
698             static RegisterAST* eip(new RegisterAST(r_EIP));
699             static RegisterAST* rip(new RegisterAST(r_RIP));
700             IPRelAddr->bind(eip, Result(s64, block.getNextAddr()));
701             IPRelAddr->bind(rip, Result(s64, block.getNextAddr()));
702             Result iprel = IPRelAddr->eval();
703             if(iprel.defined)
704             {
705                 thunkOffset = iprel.convert<Address>();
706                 parsing_printf("\tsetting thunkOffset to 0x%lx at 0x%lx\n",thunkOffset, block.getAddr());
707                 Address ret = block.getAddr();
708                 delete blockptr;
709                 return ret;
710             }
711         }
712         block.advance();
713     }
714     delete blockptr;
715     return 0;
716 }
717
718
719 std::pair<Address, Address> IA_IAPI::findThunkAndOffset(image_basicBlock* start) const
720 {
721     std::set<image_basicBlock*> visited;
722     std::deque<image_basicBlock*> worklist;
723     pdvector<image_edge*> sources;
724     image_basicBlock* curBlock;
725     worklist.insert(worklist.begin(), start);
726     visited.insert(start);
727     Address thunkOffset = 0;
728     while(!worklist.empty())
729     {
730         curBlock = worklist.front();
731         worklist.pop_front();
732         // If the only thunk we can find within this function that precedes the
733         // indirect jump in control flow (we think) is after it in the address space,
734         // it may be a jump table but it's not one our heuristics should expect to
735         // handle well.  Better to bail out than try to parse something that will be garbage.
736         if(curBlock->firstInsnOffset() > start->firstInsnOffset()) continue;
737         Address tableInsnAddr = findThunkInBlock(curBlock, thunkOffset);
738         if(tableInsnAddr != 0)
739         {
740             return std::make_pair(tableInsnAddr, thunkOffset);
741         }
742
743         sources.clear();
744         curBlock->getSources(sources);
745         for (unsigned i=0; i<sources.size(); i++) {
746             image_edge *e = sources[i];
747             if(detail::isNonCallEdge(e) && !detail::leadsToVisitedBlock(e, visited))
748             {
749                 worklist.push_back(e->getSource());
750                 visited.insert(e->getSource());
751             }
752         }
753     }
754     return std::make_pair(0, 0);
755
756 }
757
758 boost::tuple<Instruction::Ptr,
759  Instruction::Ptr,
760  bool> IA_IAPI::findMaxSwitchInsn(image_basicBlock *start) const
761 {
762     std::set<image_basicBlock *> visited;
763     std::vector<image_basicBlock *> WL;
764     std::vector<image_edge *> sources;
765     std::vector<image_edge *> targets;
766     image_basicBlock *curBlk;
767     int depth = 0;
768
769     bool foundMaxSwitch = false;
770     bool foundCondBranch = false;
771     Address maxSwitchAddr = 0;
772
773     WL.push_back(start);
774     Instruction::Ptr compareInsn, condBranchInsn;
775     bool compareOnTakenBranch = false;
776     for(unsigned j=0;j < WL.size(); j++)
777     {
778         curBlk = WL[j];
779         visited.insert(curBlk);
780
781         foundMaxSwitch = false;
782         foundCondBranch = false;
783         const unsigned char* buf =
784                 (const unsigned char*)(img->getPtrToInstruction(curBlk->firstInsnOffset()));
785         InstructionDecoder dec(buf, curBlk->getSize());
786         dec.setMode(img->getAddressWidth() == 8);
787         Instruction::Ptr i;
788         Address curAdr = curBlk->firstInsnOffset();
789         while(i = dec.decode())
790         {
791             if(i->getCategory() == c_CompareInsn)
792             // check for cmp
793             {
794                 parsing_printf("\tFound jmp table cmp instruction %s at 0x%lx\n",
795                                i->format().c_str(), curAdr);
796                 compareInsn = i;
797                 maxSwitchAddr = curAdr;
798                 foundMaxSwitch = true;
799             }
800             if(i->getCategory() == c_BranchInsn &&
801                i->allowsFallThrough())
802             {
803                 parsing_printf("\tFound jmp table cond br instruction %s at 0x%lx\n",
804                                i->format().c_str(), curAdr);
805                 condBranchInsn = i;
806                 foundCondBranch = true;
807
808                 targets.clear();
809                 curBlk->getTargets(targets);
810                 bool taken_hit = false;
811                 bool fallthrough_hit = false;
812                 for (unsigned i=0; i<targets.size(); i++) {
813                     if (targets[i]->getType() == ET_COND_TAKEN &&
814                         (visited.find(targets[i]->getTarget()) != visited.end()))
815                     {
816                         taken_hit = true;
817                     }
818                     if ((targets[i]->getType() == ET_COND_NOT_TAKEN ||
819                          targets[i]->getType() == ET_FALLTHROUGH) &&
820                          (visited.find(targets[i]->getTarget()) != visited.end()))
821                     {
822                         fallthrough_hit = true;
823                     }
824                 }
825                 parsing_printf("\tfindMaxSwitchInsn: taken_hit: %d, fallthrough_hit: %d\n", taken_hit, fallthrough_hit);
826                 compareOnTakenBranch = taken_hit && !fallthrough_hit;
827                 break;
828             }
829             curAdr += i->size();
830         }
831
832         if(foundMaxSwitch && foundCondBranch)
833             break; // done
834
835             // look further back
836         sources.clear();
837         curBlk->getSources( sources );
838         depth++;
839             // We've seen depth 2 in libc et al
840         if(depth > 2) return boost::make_tuple(Instruction::Ptr(), Instruction::Ptr(), false);
841             
842         for(unsigned i=0;i<sources.size();i++)
843         {
844             if(sources[i]->getType() == ET_CALL)
845                 return boost::make_tuple(Instruction::Ptr(), Instruction::Ptr(), false);
846
847             image_basicBlock * src = sources[i]->getSource();
848             if( (visited.find( src ) == visited.end())) {
849                 WL.push_back(src);
850             }
851         }
852     }
853     WL.clear();
854     parsing_printf("\tfindMaxSwitchInsn: table on taken branch: %d, returning: %d\n", compareOnTakenBranch, foundMaxSwitch &&
855             foundCondBranch);
856     
857     return boost::make_tuple(compareInsn, condBranchInsn, compareOnTakenBranch);
858 }
859  
860 Address IA_IAPI::getTableAddress(Instruction::Ptr tableInsn, Address thunkOffset) const
861 {
862     // Extract displacement from table insn
863     Expression::Ptr displacementSrc;
864     if(tableInsn->getCategory() == c_BranchInsn)
865     {
866         Expression::Ptr op = tableInsn->getOperand(0).getValue();
867         std::vector<InstructionAST::Ptr> tmp;
868         op->getChildren(tmp);
869         if(tmp.empty())
870         {
871             displacementSrc = op;
872         }
873         else
874         {
875             displacementSrc = dyn_detail::boost::dynamic_pointer_cast<Expression>(tmp[0]);
876         }
877     }
878     else
879     {
880         parsing_printf("\tcracking table instruction %s\n", tableInsn->format().c_str());
881         std::vector<InstructionAST::Ptr> tmp;
882         Expression::Ptr op = tableInsn->getOperand(1).getValue();
883         if(!op)
884         {
885             parsing_printf("\ttable insn BAD! (no second operand)\n");
886             return 0;
887         }
888         if(tableInsn->getOperation().getID() != e_lea)
889         {
890             op->getChildren(tmp);
891             if(tmp.empty())
892             {
893                 parsing_printf("\ttable insn BAD! (not LEA, second operand not a deref)\n");
894                 return 0;
895             }
896             displacementSrc = dyn_detail::boost::dynamic_pointer_cast<Expression>(tmp[0]);
897         }
898         else
899         {
900             displacementSrc = op;
901         }
902     }
903     static RegisterAST* allGPRs = new RegisterAST(r_ALLGPRS);
904     displacementSrc->bind(allGPRs, Result(u32, 0));
905
906     Result disp = displacementSrc->eval();
907     Address jumpTable = 0;
908     if(!disp.defined)
909     {
910         if(!thunkOffset)
911         {
912             parsing_printf("\ttable insn: %s, displacement %s, bind of all GPRs FAILED\n",
913                            tableInsn->format().c_str(), displacementSrc->format().c_str());
914             return 0;
915         }
916    }
917    else
918    {
919        jumpTable = disp.convert<Address>();
920    }
921    parsing_printf("\tjumpTable set to 0x%lx\n",jumpTable);
922
923     if(!jumpTable && !thunkOffset)
924     {
925         return 0;
926     }
927     jumpTable += thunkOffset;
928     parsing_printf("\tjumpTable revised to 0x%lx\n",jumpTable);
929     // On Windows, all of our other addresses have had the base address
930     // of their module subtracted off before we ever use them.  We need to fix this up
931     // to conform to that standard so that Symtab actually believes that there's code
932     // at the table's destination.
933 #if defined(os_windows)
934     jumpTable -= img->getObject()->getLoadOffset();
935 #endif
936     if( !img->isValidAddress(jumpTable) )
937 {
938         // If the "jump table" has a start address that is outside
939         // of the valid range of the binary, we can say with high
940         // probability that we have misinterpreted some other
941         // construct (such as a function pointer comparison & tail
942         // call, for example) as a jump table. Give up now.
943     return 0;
944 }
945     return jumpTable;
946 }
947
948 bool IA_IAPI::fillTableEntries(Address thunkOffset,
949                                Address tableBase,
950                                unsigned tableSize,
951                                unsigned tableStride,
952                                std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges) const
953 {
954     if( !img->isValidAddress(tableBase) )
955         {
956             return false;
957         }
958     for(unsigned int i=0; i < tableSize; i++)
959         {
960                 Address tableEntry = tableBase + (i * tableStride);
961                 Address jumpAddress = 0;
962                 
963                 if(img->isValidAddress(tableEntry))
964                 {
965                         if(tableStride == sizeof(Address)) {
966                                         // Unparseable jump table
967                                 jumpAddress = *(const Address *)img->getPtrToInstruction(tableEntry);
968                         }
969                         else {
970                                 assert(img->getPtrToInstruction(tableEntry));
971                                 jumpAddress = *(const int *)img->getPtrToInstruction(tableEntry);
972                         }
973                 }
974 #if defined(os_windows)
975                 if(img)
976                 {
977                         jumpAddress -= img->getObject()->getLoadOffset();
978                 }
979 #endif
980                 if(thunkOffset)
981                 {
982                         jumpAddress += thunkOffset;
983                 }
984                 if (!(img->isExecutableAddress(jumpAddress))) {
985                         parsing_printf("\tentry %d [0x%lx] -> 0x%lx, invalid, skipping\n",
986                                                         i, tableEntry, jumpAddress);
987                         continue;
988                 }
989
990                 parsing_printf("\tentry %d [0x%lx] -> 0x%lx\n",i,tableEntry,jumpAddress);
991
992                 outEdges.push_back(std::make_pair(jumpAddress, ET_INDIR));
993                 
994         }
995     return true;
996     
997 }
998
999
1000 bool IA_IAPI::computeTableBounds(Instruction::Ptr maxSwitchInsn,
1001                                  Instruction::Ptr branchInsn,
1002                                  Instruction::Ptr tableInsn,
1003                                  bool foundJCCAlongTaken,
1004                                  unsigned& tableSize,
1005                                  unsigned& tableStride) const
1006 {
1007     assert(maxSwitchInsn && branchInsn);
1008     Result compareBound = maxSwitchInsn->getOperand(1).getValue()->eval();
1009     if(!compareBound.defined) return false;
1010     tableSize = compareBound.convert<unsigned>();
1011     // Sanity check the bounds; 32k tables would be an oddity, and larger is almost certainly
1012     // a misparse
1013     static const unsigned int maxTableSize = 32768;
1014     if(tableSize > maxTableSize)
1015     {
1016         parsing_printf("\tmaxSwitch of %d above %d, BAILING OUT\n", tableSize, maxTableSize);
1017         return false;
1018     }
1019     if(foundJCCAlongTaken)
1020     {
1021         if(branchInsn->getOperation().getID() == e_jbe ||
1022            branchInsn->getOperation().getID() == e_jle)
1023         {
1024             tableSize++;
1025         }
1026     }
1027     else
1028     {
1029         if(branchInsn->getOperation().getID() == e_jnbe ||
1030            branchInsn->getOperation().getID() == e_jnle)
1031         {
1032             tableSize++;
1033         }
1034     }
1035     parsing_printf("\tmaxSwitch set to %d\n", tableSize);
1036     tableStride = img->getAddressWidth();
1037     std::set<Expression::Ptr> tableInsnReadAddr;
1038     tableInsn->getMemoryReadOperands(tableInsnReadAddr);
1039     if(tableStride == 8)
1040     {
1041         static Immediate::Ptr four(new Immediate(Result(u8, 4)));
1042         static BinaryFunction::funcT::Ptr multiplier(new BinaryFunction::multResult());
1043         static Expression::Ptr dummy(new DummyExpr());
1044         static BinaryFunction::Ptr scaleCheck(new BinaryFunction(four, dummy, u64, multiplier));
1045         for(std::set<Expression::Ptr>::const_iterator curExpr = tableInsnReadAddr.begin();
1046             curExpr != tableInsnReadAddr.end();
1047             ++curExpr)
1048         {
1049             if((*curExpr)->isUsed(scaleCheck))
1050             {
1051                 tableSize = tableSize >> 1;
1052                 parsing_printf("\tmaxSwitch revised to %d\n",tableSize);
1053             }
1054         }
1055     }
1056     return true;
1057 }
1058
1059 Instruction::Ptr IA_IAPI::curInsn() const
1060 {
1061     return curInsnIter->second;
1062 }
1063
1064 bool IA_IAPI::isLeave() const
1065 {
1066     return curInsn() &&
1067             (curInsn()->getOperation().getID() == e_leave);
1068 }
1069
1070 bool IA_IAPI::isDelaySlot() const
1071 {
1072 #if defined(arch_sparc)
1073     assert(!"Implement delay slots on SPARC!");
1074 #endif
1075     return false;
1076 }
1077
1078 Instruction::Ptr IA_IAPI::getInstruction()
1079 {
1080     return curInsn();
1081 }
1082
1083 bool IA_IAPI::isRealCall() const
1084 {
1085     if(getCFT() == getNextAddr())
1086     {
1087         parsing_printf("... getting PC\n");
1088         return false;
1089     }
1090     if(!img->isValidAddress(getCFT()))
1091     {
1092         parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
1093                        getCFT());
1094         return false;
1095     }
1096     const unsigned char *target =
1097             (const unsigned char *)img->getPtrToInstruction(getCFT());
1098
1099     // We're decoding two instructions: possible move and possible return.
1100     // Check for move from the stack pointer followed by a return.
1101     InstructionDecoder targetChecker(target, 32);
1102     targetChecker.setMode(img->getAddressWidth() == 8);
1103     Instruction::Ptr thunkFirst = targetChecker.decode();
1104     Instruction::Ptr thunkSecond = targetChecker.decode();
1105     parsing_printf("... checking call target for thunk, insns are %s, %s\n", thunkFirst->format().c_str(),
1106                    thunkSecond->format().c_str());
1107     if(thunkFirst && (thunkFirst->getOperation().getID() == e_mov))
1108     {
1109         RegisterAST::Ptr esp(new RegisterAST(r_ESP));
1110         RegisterAST::Ptr rsp(new RegisterAST(r_RSP));
1111         if(thunkFirst->isRead(esp) || thunkFirst->isRead(rsp))
1112         {
1113             parsing_printf("... checking second insn\n");
1114             if(!thunkSecond) {
1115                 parsing_printf("...no second insn\n");
1116                 return true;
1117             }
1118             if(thunkSecond->getCategory() != c_ReturnInsn)
1119             {
1120                 parsing_printf("...insn %s not a return\n", thunkSecond->format().c_str());
1121                 return true;
1122             }
1123             return false;
1124         }
1125     }
1126     parsing_printf("... real call found\n");
1127     return true;
1128 }
1129
1130 bool IA_IAPI::isConditional() const
1131 {
1132     return curInsn()->allowsFallThrough();
1133 }
1134
1135 bool IA_IAPI::simulateJump() const
1136 {
1137     // TODO: we don't simulate jumps on x86 architectures; add logic as we need it.                
1138     return false;
1139 }
1140
1141 Address IA_IAPI::getCFT() const
1142 {
1143     static RegisterAST thePC = RegisterAST::makePC();
1144     static RegisterAST* rip = new RegisterAST(r_RIP);
1145     if(validCFT) return cachedCFT;
1146     Expression::Ptr callTarget = curInsn()->getControlFlowTarget();
1147         // FIXME: templated bind(),dammit!
1148     callTarget->bind(&thePC, Result(s64, current));
1149     callTarget->bind(rip, Result(s64, current));
1150     parsing_printf("%s[%d]: binding PC in %s to 0x%x...", FILE__, __LINE__,
1151                    curInsn()->format().c_str(), current);
1152     Result actualTarget = callTarget->eval();
1153     if(actualTarget.defined)
1154     {
1155         cachedCFT = actualTarget.convert<Address>();
1156         parsing_printf("SUCCESS (CFT=0x%x)\n", cachedCFT);
1157     }
1158     else
1159     {
1160         cachedCFT = 0;
1161         parsing_printf("FAIL (CFT=0x%x)\n", cachedCFT);
1162     }
1163     validCFT = true;
1164     return cachedCFT;
1165 }
1166
1167 bool IA_IAPI::isRelocatable(InstrumentableLevel lvl) const
1168 {
1169     if(curInsn() && (curInsn()->getCategory() == c_CallInsn))
1170     {
1171         if(!isDynamicCall())
1172         {
1173             if(!img->isValidAddress(getCFT()))
1174             {
1175                 parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
1176                                getCFT());
1177                 return false;
1178             }
1179         }
1180     }
1181     if(lvl == HAS_BR_INDIR)
1182     {
1183         return false;
1184     }
1185     return true;
1186 }
1187 bool IA_IAPI::isTailCall(unsigned int) const
1188 {
1189     if(tailCall.first) {
1190         parsing_printf("\tReturning cached tail call check result: %d\n", tailCall.second);
1191         return tailCall.second;
1192     }
1193     tailCall.first = true;
1194     if(allInsns.size() < 2) {
1195         tailCall.second = false;
1196         parsing_printf("\tindirect jump with too few insns, not a tail call\n");
1197         return tailCall.second;
1198     }
1199     if(curInsn()->getCategory() == c_BranchInsn ||
1200        curInsn()->getCategory() == c_CallInsn)
1201     {
1202         if(curInsn()->getCategory() == c_BranchInsn)
1203         {
1204             if(img->findFuncByEntry(getCFT()))
1205             {
1206                 parsing_printf("\tjump to 0x%lx, TAIL CALL\n", getCFT());
1207                 tailCall.second = true;
1208                 return tailCall.second;
1209             }
1210         }
1211         std::map<Address, Instruction::Ptr>::const_iterator prevIter =
1212                 allInsns.find(current);
1213         --prevIter;
1214         Instruction::Ptr prevInsn = prevIter->second;
1215         if(prevInsn->getOperation().getID() == e_leave)
1216         {
1217             parsing_printf("\tprev insn was leave, TAIL CALL\n");
1218             tailCall.second = true;
1219             return tailCall.second;
1220         }
1221         if(prevInsn->getOperation().getID() == e_pop)
1222         {
1223             static RegisterAST::Ptr ebp(new RegisterAST(r_EBP));
1224             static RegisterAST::Ptr rbp(new RegisterAST(r_RBP));
1225             static RegisterAST::Ptr xbp(new RegisterAST(r_eBP));
1226             static RegisterAST::Ptr rxbp(new RegisterAST(r_rBP));
1227             if(prevInsn->isWritten(ebp) || prevInsn->isWritten(rbp) ||
1228                prevInsn->isWritten(xbp) || prevInsn->isWritten(rxbp))
1229             {
1230                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
1231                 tailCall.second = true;
1232                 return tailCall.second;
1233             }
1234             parsing_printf("\tprev insn was %s, not tail call\n", prevInsn->format().c_str());
1235         }
1236     }
1237     tailCall.second = false;
1238     return tailCall.second;
1239 }
1240
1241 bool IA_IAPI::checkEntry() const
1242 {
1243     if(curInsn()->getCategory() == c_BranchInsn)
1244     {
1245         // Indirect branches are okay; 
1246         if(!curInsn()->allowsFallThrough() && getCFT())
1247         {
1248             return false;
1249         }
1250     }
1251     if(curInsn()->getCategory() == c_ReturnInsn)
1252     {
1253         return false;
1254     }
1255     // We don't consider linkage snippets "functions".
1256     dictionary_hash<Address, std::string> *pltFuncs = img->getPltFuncs();
1257     if (pltFuncs && pltFuncs->defines(getAddr())) 
1258     {
1259         return false;
1260     }
1261
1262     return true;
1263 }
1264
1265 bool IA_IAPI::savesFP() const
1266 {
1267     if(curInsn()->getOperation().getID() == e_push)
1268     {
1269         static RegisterAST::Ptr ebp(new RegisterAST(r_EBP));
1270         static RegisterAST::Ptr rbp(new RegisterAST(r_RBP));
1271         return(curInsn()->isRead(ebp) || curInsn()->isRead(rbp));
1272     }
1273     return false;
1274 }
1275
1276 bool IA_IAPI::isStackFramePreamble(int& /*frameSize*/) const
1277 {
1278     if(savesFP())
1279     {
1280         InstructionDecoder tmp(dec);
1281         std::vector<Instruction::Ptr> nextTwoInsns;
1282         nextTwoInsns.push_back(tmp.decode());
1283         nextTwoInsns.push_back(tmp.decode());
1284         if(isFrameSetupInsn(nextTwoInsns[0]) ||
1285             isFrameSetupInsn(nextTwoInsns[1]))
1286         {
1287             return true;
1288         }
1289     }
1290     return false;
1291 }
1292
1293 InstrumentableLevel IA_IAPI::getInstLevel(unsigned int num_insns) const
1294 {
1295     InstrumentableLevel ret = InstructionAdapter::getInstLevel( num_insns);
1296 /*    if(ret == HAS_BR_INDIR && isIPRelativeBranch())
1297     {
1298         return NORMAL;
1299 }*/
1300     return ret;
1301 }
1302
1303         
1304 bool IA_IAPI::cleansStack() const
1305 {
1306     return (curInsn()->getCategory() == c_ReturnInsn) &&
1307             curInsn()->getOperand(0).getValue();
1308
1309 }
1310