Slight optimization: statically construct stack pointer/frame pointer/PC ASTs.
[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 #include <boost/assign/list_of.hpp>
44
45 using namespace Dyninst;
46 using namespace InstructionAPI;
47
48 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::framePtr = boost::assign::map_list_of
49         (Arch_x86, RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86))))
50         (Arch_x86_64, RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86_64))))
51         (Arch_ppc32, RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc32))))
52         (Arch_ppc64, RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc64))));
53 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::stackPtr = boost::assign::map_list_of
54         (Arch_x86, RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86))))
55         (Arch_x86_64, RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86_64))))
56         (Arch_ppc32, RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc32))))
57         (Arch_ppc64, RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc64))));
58 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::thePC = boost::assign::map_list_of
59         (Arch_x86, RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86))))
60         (Arch_x86_64, RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86_64))))
61         (Arch_ppc32, RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc32))))
62         (Arch_ppc64, RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc64))));
63
64 IA_IAPI::IA_IAPI(InstructionDecoder dec_, Address where_,
65                 image_func* f)
66     : InstructionAdapter(where_, f), dec(dec_),
67     validCFT(false), cachedCFT(0)
68 {
69     hascftstatus.first = false;
70     tailCall.first = false;
71     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
72 }
73
74 IA_IAPI::IA_IAPI(InstructionDecoder dec_, Address where_,
75                 image * im)
76     : InstructionAdapter(where_, im), dec(dec_),
77     validCFT(false), cachedCFT(0)
78 {
79     hascftstatus.first = false;
80     tailCall.first = false;
81     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
82 }
83
84 void IA_IAPI::advance()
85 {
86     if(!curInsn()) {
87         parsing_printf("..... WARNING: failed to advance InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
88                        allInsns.size());
89         return;
90     }
91     InstructionAdapter::advance();
92     current += curInsn()->size();
93     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
94     if(!curInsn())
95     {
96         parsing_printf("......WARNING: after advance at 0x%lx, curInsn() NULL\n", current);
97     }
98     validCFT = false;
99     hascftstatus.first = false;
100     tailCall.first = false;
101 }
102
103 size_t IA_IAPI::getSize() const
104 {
105     assert(curInsn());
106     return curInsn()->size();
107 }
108
109 bool IA_IAPI::hasCFT() const
110 {
111     if(hascftstatus.first) return hascftstatus.second;
112     InsnCategory c = curInsn()->getCategory();
113     hascftstatus.second = false;
114     if(c == c_BranchInsn ||
115        c == c_ReturnInsn)
116     {
117         hascftstatus.second = true;
118     }
119     if(c == c_CallInsn)
120     {
121         if(isRealCall()) {
122             hascftstatus.second = true;
123         }
124         if(isDynamicCall()) {
125             hascftstatus.second = true;
126         }
127         if(simulateJump()) {
128             hascftstatus.second = true;
129         }
130     }
131     hascftstatus.first = true;
132     return hascftstatus.second;
133 }
134
135 bool IA_IAPI::isAbortOrInvalidInsn() const
136 {
137     entryID e = curInsn()->getOperation().getID();
138     if(e == e_No_Entry)
139     {
140         parsing_printf("...WARNING: un-decoded instruction at 0x%x\n", current);
141     }
142     return e == e_No_Entry ||
143             e == e_int3 ||
144             e == e_hlt;
145 }
146
147 bool IA_IAPI::isAllocInsn() const
148 {
149 #if !defined(arch_ia64)
150     // IA64 only
151     return false;
152 #else
153     assert(!"Implement for IA64\n");
154     return false;
155 #endif
156 }
157
158
159 bool IA_IAPI::isFrameSetupInsn() const
160 {
161     return isFrameSetupInsn(curInsn());
162 }
163
164 bool IA_IAPI::isDynamicCall() const
165 {
166     if(curInsn() && (curInsn()->getCategory() == c_CallInsn))
167     {
168         if(getCFT() == 0)
169         {
170             parsing_printf("... Call 0x%lx is indirect\n", current);
171             return true;
172         }
173     }
174     return false;
175 }
176
177 bool IA_IAPI::isAbsoluteCall() const
178 {
179     if(curInsn()->getCategory() == c_CallInsn)
180     {
181         Expression::Ptr cft = curInsn()->getControlFlowTarget();
182         if(cft && dyn_detail::boost::dynamic_pointer_cast<Immediate>(cft))
183         {
184             return true;
185         }
186     }
187     return false;
188 }
189
190
191 bool IA_IAPI::isReturn() const
192 {
193     return curInsn()->getCategory() == c_ReturnInsn;
194 }
195 bool IA_IAPI::isBranch() const
196 {
197     return curInsn()->getCategory() == c_BranchInsn;
198 }
199 bool IA_IAPI::isCall() const
200 {
201     return curInsn()->getCategory() == c_CallInsn;
202 }
203
204 bool IA_IAPI::isInterruptOrSyscall() const
205 {
206     return (isInterrupt() && isSyscall());
207 }
208
209 bool IA_IAPI::isSyscall() const
210 {
211     static RegisterAST::Ptr gs(new RegisterAST(x86::gs));
212
213     return (((curInsn()->getOperation().getID() == e_call) &&
214             /*(curInsn()->getOperation().isRead(gs))) ||*/
215             (curInsn()->getOperand(0).format() == "16")) ||
216             (curInsn()->getOperation().getID() == e_syscall) || 
217             (curInsn()->getOperation().getID() == e_int) || 
218             (curInsn()->getOperation().getID() == power_op_sc));
219 }
220
221
222 bool IA_IAPI::isInterrupt() const
223 {
224     return ((curInsn()->getOperation().getID() == e_int) ||
225             (curInsn()->getOperation().getID() == e_int3));
226 }
227
228 void IA_IAPI::getNewEdges(
229         pdvector<std::pair< Address, EdgeTypeEnum> >& outEdges,
230         image_basicBlock* currBlk,
231         unsigned int num_insns,
232         dictionary_hash<Address,
233         std::string> *pltFuncs) const
234 {
235     if(!context) {
236         fprintf(stderr, "[%s] getNewEdges not supported in non-image_func"
237                         "context\n", FILE__);
238         return;
239     }
240
241     // Only call this on control flow instructions!
242     if(curInsn()->getCategory() == c_CallInsn)
243     {
244         Address target = getCFT();
245         if(isRealCall())
246         {
247             outEdges.push_back(std::make_pair(target, ET_NOEDGE));
248         }
249         else
250         {
251             if(img->isValidAddress(getCFT()))
252             {
253                 if(simulateJump())
254                 {
255                     parsing_printf("[%s:%u] call at 0x%lx simulated as "
256                             "jump to 0x%lx\n",
257                     FILE__,__LINE__,getAddr(),getCFT());
258                     outEdges.push_back(std::make_pair(target, ET_DIRECT));
259                     return;
260                 }
261             }
262         }
263         outEdges.push_back(std::make_pair(getAddr() + getSize(),
264                            ET_FUNLINK));
265         return;
266     }
267     else if(curInsn()->getCategory() == c_BranchInsn)
268     {
269         if(curInsn()->allowsFallThrough())
270         {
271             outEdges.push_back(std::make_pair(getCFT(),
272                                ET_COND_TAKEN));
273             outEdges.push_back(std::make_pair(getNextAddr(), ET_COND_NOT_TAKEN));
274             return;
275         }
276         // Direct jump
277         else if(getCFT() != 0)
278         {
279             Address catchStart;
280             if(context->archProcExceptionBlock(catchStart, getNextAddr()))
281             {
282                 outEdges.push_back(std::make_pair(catchStart, ET_CATCH));
283             }
284         
285
286             if(!isTailCall(num_insns))
287             {
288                 if(!(*pltFuncs).defines(getCFT()))
289                 {
290                     outEdges.push_back(std::make_pair(getCFT(),
291                                        ET_DIRECT));
292                 }
293                 else
294                 {
295                     parsing_printf("%s[%d]: PLT tail call to %x\n", FILE__, __LINE__, getCFT());
296                     outEdges.push_back(std::make_pair(getCFT(), ET_NOEDGE));
297                     tailCall.second = true;
298                 }
299             }
300             else
301             {
302                 parsing_printf("%s[%d]: tail call to %x\n", FILE__, __LINE__, getCFT());
303                 outEdges.push_back(std::make_pair(getCFT(), ET_NOEDGE));
304             }
305             return;
306         }
307         else
308         {
309             parsing_printf("... indirect jump at 0x%x\n", current);
310             if( num_insns == 2 ) {
311                 parsing_printf("... uninstrumentable due to 0 size\n");
312                 return;
313             }
314             if(isTailCall(num_insns)) {
315                 parsing_printf("%s[%d]: indirect tail call %s at 0x%lx\n", FILE__, __LINE__,
316                                curInsn()->format().c_str(), current);
317                 return;
318             }
319             parsing_printf("%s[%d]: jump table candidate %s at 0x%lx\n", FILE__, __LINE__,
320                            curInsn()->format().c_str(), current);
321             parsedJumpTable = true;
322             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
323             return;
324         }
325     }
326     else if(curInsn()->getCategory() == c_ReturnInsn)
327     {
328         if(curInsn()->allowsFallThrough())
329         {
330             outEdges.push_back(std::make_pair(getNextAddr(), ET_FALLTHROUGH));
331             return;
332         }
333         return;
334     }
335     fprintf(stderr, "Unhandled instruction %s\n", curInsn()->format().c_str());
336     assert(0);
337 }
338
339
340 bool IA_IAPI::isIPRelativeBranch() const
341 {
342             // These don't exist on IA32...
343 #if !defined(arch_x86_64)
344     return false;
345 #endif
346     if(curInsn()->getCategory() == c_BranchInsn &&
347         !getCFT())
348 {
349     Expression::Ptr cft = curInsn()->getControlFlowTarget();
350     if(cft->isUsed(thePC[img->getArch()]))
351     {
352         parsing_printf("\tIP-relative indirect jump to %s at 0x%lx\n",
353                        cft->format().c_str(), current);
354         return true;
355     }
356 }
357     return false;
358     
359 }
360
361
362 Instruction::Ptr IA_IAPI::curInsn() const
363 {
364     return curInsnIter->second;
365 }
366
367 bool IA_IAPI::isLeave() const
368 {
369     return curInsn() &&
370             (curInsn()->getOperation().getID() == e_leave);
371 }
372
373 bool IA_IAPI::isDelaySlot() const
374 {
375 #if defined(arch_sparc)
376     assert(!"Implement delay slots on SPARC!");
377 #endif
378     return false;
379 }
380
381 Instruction::Ptr IA_IAPI::getInstruction()
382 {
383     return curInsn();
384 }
385
386 bool IA_IAPI::isRealCall() const
387 {
388     if(getCFT() == getNextAddr())
389     {
390         parsing_printf("... getting PC\n");
391         return false;
392     }
393     if(!img->isValidAddress(getCFT()))
394     {
395         return false;
396     }
397
398     return (!isThunk());
399 }
400
401
402 std::map<Address, bool> IA_IAPI::thunkAtTarget;
403
404 bool IA_IAPI::isConditional() const
405 {
406     return curInsn()->allowsFallThrough();
407 }
408
409 bool IA_IAPI::simulateJump() const
410 {
411     // TODO: we don't simulate jumps on x86 architectures; add logic as we need it.                
412     return false;
413 }
414
415 Address IA_IAPI::getCFT() const
416 {
417     if(validCFT) return cachedCFT;
418     Expression::Ptr callTarget = curInsn()->getControlFlowTarget();
419         // FIXME: templated bind(),dammit!
420     callTarget->bind(thePC[img->getArch()].get(), Result(s64, current));
421     parsing_printf("%s[%d]: binding PC %s in %s to 0x%x...", FILE__, __LINE__,
422                    thePC[img->getArch()]->format().c_str(), curInsn()->format().c_str(), current);
423     Result actualTarget = callTarget->eval();
424     if(actualTarget.defined)
425     {
426         cachedCFT = actualTarget.convert<Address>();
427         parsing_printf("SUCCESS (CFT=0x%x)\n", cachedCFT);
428     }
429     else
430     {
431         cachedCFT = 0;
432         parsing_printf("FAIL (CFT=0x%x)\n", cachedCFT);
433     }
434     validCFT = true;
435     return cachedCFT;
436 }
437
438 bool IA_IAPI::isRelocatable(InstrumentableLevel lvl) const
439 {
440     if(curInsn() && (curInsn()->getCategory() == c_CallInsn))
441     {
442         if(!isDynamicCall())
443         {
444             if(!img->isValidAddress(getCFT()))
445             {
446                 parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
447                                getCFT());
448                 return false;
449             }
450         }
451     }
452     if(lvl == HAS_BR_INDIR)
453     {
454         return false;
455     }
456     return true;
457 }
458
459
460 InstrumentableLevel IA_IAPI::getInstLevel(unsigned int num_insns) const
461 {
462     InstrumentableLevel ret = InstructionAdapter::getInstLevel( num_insns);
463 /*    if(ret == HAS_BR_INDIR && isIPRelativeBranch())
464     {
465         return NORMAL;
466 }*/
467     return ret;
468 }
469
470         
471