fixing stuff
[dyninst.git] / parseAPI / src / IA_power.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
33 #include "IA_IAPI.h"
34
35 #include "Register.h"
36 #include "Dereference.h"
37 #include "Immediate.h"
38 #include "BinaryFunction.h"
39
40 #include "common/h/arch.h"
41
42 #include "parseAPI/src/debug_parse.h"
43
44 #include <deque>
45 #include <iostream>
46 #include <sstream>
47 #include <functional>
48 #include <algorithm>
49 #include <set>
50
51 using namespace Dyninst;
52 using namespace InstructionAPI;
53 using namespace Dyninst::ParseAPI;
54 using namespace Dyninst::InsnAdapter;
55
56 bool IA_IAPI::isFrameSetupInsn(Instruction::Ptr) const
57 {
58     return false;
59 }
60
61 bool IA_IAPI::isNop() const
62 {
63     return false;
64 }
65
66 bool IA_IAPI::isMovAPSTable(std::vector<std::pair< Address, EdgeTypeEnum > >&) const
67 {
68     return false;
69 }
70
71 bool IA_IAPI::isTableInsn(Instruction::Ptr) const
72 {
73     return false;
74 }
75         
76 std::map<Address, Instruction::Ptr>::const_iterator IA_IAPI::findTableInsn() const
77 {
78     return allInsns.end();
79 }
80
81 namespace detail
82 {
83     bool isNonCallEdge(Edge* e)
84     {
85         return e->type() != CALL;
86     }
87     bool leadsToVisitedBlock(Edge* e, const std::set<Block*>& visited)
88     {
89         Block* src = e->src();
90         return visited.find(src) != visited.end();
91     }
92
93     class TOCandOffsetExtractor : public Dyninst::InstructionAPI::Visitor
94     {
95         public:
96             TOCandOffsetExtractor(Address TOCvalue) : toc_contents(TOCvalue) {}
97             virtual ~TOCandOffsetExtractor() {}
98             virtual void visit(BinaryFunction* b) {
99                 Address arg1 = m_stack.front();
100                 m_stack.pop_front();
101                 Address arg2 = m_stack.front();
102                 m_stack.pop_front();
103                 if(b->isAdd()) {
104                     result = arg1 + arg2;
105                 } else if(b->isMultiply()) {
106                     result = arg1 * arg2;
107                 } else {
108                     assert(!"unexpected binary function!");
109                     result = 0;
110                 }
111                 parsing_printf("\tTOC visitor visiting binary function, result is 0x%lx\n",
112                             result);
113                 m_stack.push_front(result);
114             }
115             virtual void visit(Immediate* i) {
116                 Address tmp = i->eval().convert<Address>();
117                 result = tmp;
118                 parsing_printf("\tTOC visitor visiting immediate, result is 0x%lx\n",
119                             result);
120                 m_stack.push_front(tmp);   
121             }
122             virtual void visit(RegisterAST* r) {
123                 if(r->getID() == ppc32::r2) {
124                     m_stack.push_front(toc_contents);
125                 } else {
126                     m_stack.push_front(0);
127                 }
128                 result = m_stack.front();
129                 parsing_printf("\tTOC visitor visiting register, result is 0x%lx\n",
130                             result);
131             }
132             virtual void visit(Dereference*) {}
133             void clear() {
134                 m_stack.clear();
135                 result = 0;
136             }
137             std::deque<Address> m_stack;
138             Address result;
139             Address toc_contents;
140     };
141 };
142
143
144
145
146 // This should only be called on a known indirect branch...
147 bool IA_IAPI::parseJumpTable(Block* currBlk,
148     std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges) const
149 {
150
151 Address initialAddress = current;
152 static RegisterAST::Ptr toc_reg(new RegisterAST(ppc32::r2));
153
154 Address TOC_address = _obj->cs()->getTOC();
155 detail::TOCandOffsetExtractor toc_visitor(TOC_address);
156     
157 // If there are no prior instructions then we can't be looking at a
158 // jump through a jump table.
159 if(allInsns.size() < 2) {
160     parsing_printf("%s[%d]: allInsns.size() == %d, ret false", FILE__, __LINE__, allInsns.size());
161     return false;
162 }
163
164
165 // Check if the previous instruction is a move to CTR or LR;
166 // if it is, then this is the pattern we're familiar with.  The
167 // register being moved into CTR or LR has the address to jump to.
168 std::map<Address, Instruction::Ptr>::const_iterator patternIter = curInsnIter;
169 patternIter--;
170 RegisterAST::Ptr jumpAddrReg;
171 static RegisterAST::Ptr linkReg(new RegisterAST(ppc32::lr));
172 static RegisterAST::Ptr countReg(new RegisterAST(ppc32::ctr));
173 std::set<RegisterAST::Ptr> regs;
174 if(patternIter->second->getOperation().getID() == power_op_mtspr &&
175     (patternIter->second->isWritten(linkReg) ||
176     patternIter->second->isWritten(countReg)))
177 {
178     regs.clear();
179     patternIter->second->getReadSet(regs);
180     if(regs.size() != 1) {
181         fprintf(stderr, "expected mtspr to read 1 register, insn is %s\n", patternIter->second->format().c_str());
182         return false;
183     }
184     jumpAddrReg = *(regs.begin());
185 }
186 else
187 {
188     parsing_printf("%s[%d]: couldn't find mtspr at prev insn %s, ret false", FILE__, __LINE__,
189                     patternIter->second->format().c_str());
190     return false;
191 }
192 // In the pattern we've seen, if the instruction previous to this is
193 // an add with a result that ends up being used as the jump address,
194 // then we're adding a relative value we got from the table to a base
195 // address to get the jump address; in other words, the contents of
196 // the jump table are relative.
197 bool tableIsRelative = false;
198 if(patternIter != allInsns.begin())
199 {
200     patternIter--;
201     if(patternIter->second->getOperation().getID() == power_op_add &&
202         patternIter->second->isWritten(*(regs.begin())))
203     {
204         tableIsRelative = true;
205     }
206 }
207
208 patternIter = curInsnIter;
209     
210 Address jumpStartAddress = 0;
211 Address adjustEntry = 0;
212 Address tableStartAddress = 0;
213 if(!TOC_address)
214 {
215     while(patternIter != allInsns.begin())
216     {
217     patternIter--;
218     if(patternIter->second->getOperation().getID() == power_op_addi)
219     {
220         regs.clear();
221         patternIter->second->getReadSet(regs);
222         if(regs.size() != 1) {
223         continue;
224         }
225         parsing_printf("\tfound 0x%lx: %s, checking for addis previous\n",
226                     patternIter->first,
227                     patternIter->second->format().c_str());
228         toc_visitor.clear();
229         patternIter->second->getOperand(2).getValue()->apply(&toc_visitor);
230         tableStartAddress = toc_visitor.result;
231         patternIter--;
232         if(patternIter->second->getOperation().getID() == power_op_addis &&
233         patternIter->second->isWritten(*(regs.begin())))
234         {
235             parsing_printf("\tfound 0x%lx: %s, setting tableStartAddress\n",
236                         patternIter->first,
237                         patternIter->second->format().c_str());
238             toc_visitor.clear();
239             patternIter->second->getOperand(2).getValue()->apply(&toc_visitor);
240             tableStartAddress += (toc_visitor.result * 0x10000) & 0xFFFF0000;
241             parsing_printf("\ttableStartAddress = 0x%lx\n",
242                         tableStartAddress);
243             break;
244         }
245         tableStartAddress = 0;
246     }
247     else if(patternIter->second->getOperation().getID() == power_op_addis)
248     {
249         regs.clear();
250         patternIter->second->getReadSet(regs);
251         if(regs.size() != 1) {
252             continue;
253         }
254         parsing_printf("\tfound 0x%lx: %s, checking for addi previous\n",
255                         patternIter->first,
256                         patternIter->second->format().c_str());
257         toc_visitor.clear();
258         patternIter->second->getOperand(2).getValue()->apply(&toc_visitor);
259         tableStartAddress = toc_visitor.result;
260         tableStartAddress *= 10000;
261         tableStartAddress &= 0xFFFF0000;
262         patternIter--;
263         if(patternIter->second->getOperation().getID() == power_op_addi &&
264             patternIter->second->isWritten(*(regs.begin())))
265         {
266             parsing_printf("\tfound 0x%lx: %s, setting tableStartAddress\n",
267                             patternIter->first,
268                             patternIter->second->format().c_str());
269             toc_visitor.clear();
270             patternIter->second->getOperand(2).getValue()->apply(&toc_visitor);
271             tableStartAddress += toc_visitor.result;
272                     parsing_printf("\ttableStartAddress = 0x%lx\n", tableStartAddress);
273                     break;
274                 }
275                 tableStartAddress = 0;
276             }
277         }
278         jumpStartAddress = tableStartAddress;
279     }
280     else if (tableIsRelative) {
281         while(patternIter != allInsns.begin())
282         {
283             patternIter--;
284             if((patternIter->second->getOperation().getID() == power_op_lwz ||
285                 patternIter->second->getOperation().getID() == power_op_ld) &&
286                 patternIter->second->isRead(toc_reg))
287             {
288                 toc_visitor.clear();
289                 patternIter->second->getOperand(1).getValue()->apply(&toc_visitor);
290                 jumpStartAddress = toc_visitor.result;
291                 break;
292             }
293         }
294         if(patternIter == allInsns.begin())
295         {
296             // If we've already backed up to the beginning, we're not going to find a legit table
297             // start address; bail now.
298             parsing_printf("%s[%d]: jumpStartAddress insn was first in block w/relative table, ret false\n",
299                            FILE__, __LINE__);
300             return false;
301         }
302     // Anyone know what this does?
303         patternIter--;
304         if((patternIter->second->getOperation().getID() == power_op_lwz ||
305             patternIter->second->getOperation().getID() == power_op_ld))
306         {
307             toc_visitor.clear();
308             patternIter->second->getOperand(1).getValue()->apply(&toc_visitor);
309             adjustEntry = toc_visitor.result;
310         }
311
312         while(patternIter != allInsns.begin()){
313             patternIter--;
314             if((patternIter->second->getOperation().getID() == power_op_lwz ||
315                 patternIter->second->getOperation().getID() == power_op_ld) &&
316                 patternIter->second->isRead(toc_reg))
317             {
318                 toc_visitor.clear();
319                 patternIter->second->getOperand(1).getValue()->apply(&toc_visitor);
320                 tableStartAddress = toc_visitor.result;
321                 break;
322             }
323         }
324     } else {
325         bool foundAdjustEntry = false;
326         while( patternIter != allInsns.begin() )
327         {
328             if(patternIter->second->getOperation().getID() == power_op_addi &&
329                 patternIter->second->isWritten(jumpAddrReg) &&
330                 !foundAdjustEntry)
331             {
332                 foundAdjustEntry = true;
333                 toc_visitor.clear();
334                 patternIter->second->getOperand(1).getValue()->apply(&toc_visitor);
335                 adjustEntry = toc_visitor.result;
336                 regs.clear();
337                 patternIter->second->getReadSet(regs);
338                 jumpAddrReg = *(regs.begin());
339             }
340             else if(patternIter->second->getOperation().getID() == power_op_lwz &&
341                     patternIter->second->isRead(toc_reg) &&
342                     patternIter->second->isWritten(jumpAddrReg))
343             {
344                 toc_visitor.clear();
345                 patternIter->second->getOperand(1).getValue()->apply(&toc_visitor);
346                 tableStartAddress = toc_visitor.result;
347                 break;
348             }
349             patternIter--;
350         }
351     }
352
353 // We could also set this = jumpStartAddress...
354     if (tableStartAddress == 0)  {
355         parsing_printf("%s[%d]: couldn't find table start addr, ret false\n", FILE__, __LINE__);
356         return false;
357     }
358     parsing_printf("%s[%d]: table start addr is 0x%x\n", FILE__, __LINE__, tableStartAddress);
359     int maxSwitch = 0;
360   
361     Block::edgelist & sourceEdges = currBlk->sources();
362     if(sourceEdges.size() != 1) {
363         parsing_printf("%s[%d]: jump table not properly guarded, ret false\n", FILE__, __LINE__);
364         return false;
365     }
366     Block* sourceBlock = (*sourceEdges.begin())->src();
367     Address blockStart = sourceBlock->start();
368     const unsigned char* b = (const unsigned char*)(_isrc->getPtrToInstruction(blockStart));
369     InstructionDecoder dec(b, sourceBlock->size(), _isrc->getArch());
370     IA_IAPI prevBlock(dec, blockStart,_obj,_cr,_isrc);
371     while(!prevBlock.hasCFT()) {
372         prevBlock.advance();
373     }
374
375     parsing_printf("%s[%d]: checking for max switch...\n", FILE__, __LINE__);
376     patternIter = prevBlock.curInsnIter;
377     while( patternIter != prevBlock.allInsns.begin() ) {
378         parsing_printf("\t\tchecking insn 0x%x: %s for cond branch\n", patternIter->first,
379                             patternIter->second->format().c_str());
380         if(patternIter->second->getOperation().getID() == power_op_bc) // make this a true cond. branch check
381         {
382             if(patternIter != prevBlock.allInsns.begin())
383             {
384                 patternIter--;
385                 parsing_printf("\t\tchecking insn 0x%x: %s for compare\n", patternIter->first,
386                                 patternIter->second->format().c_str());
387                 if(patternIter->second->getOperation().getID() == power_op_cmpi ||
388                     patternIter->second->getOperation().getID() == power_op_cmpli)
389                 {
390                     maxSwitch = patternIter->second->getOperand(2).getValue()->eval().convert<int>() + 1;
391                     break;
392                 }
393             }
394             else
395             {
396                 parsing_printf("\t\t ******** prevBlock.allInsns begins with cond branch!\n");
397             }
398         }
399         patternIter--;
400     }
401
402     parsing_printf("%s[%d]: After checking: max switch %d\n", FILE__, __LINE__, maxSwitch);
403     if(!maxSwitch){
404         return false;
405     }
406
407     Address jumpStart = 0;
408     Address tableStart = 0;
409     bool is64 = (_isrc->getAddressWidth() == 8);
410
411     if(TOC_address)
412     {
413             if (tableIsRelative) {
414                 void *jumpStartPtr = _isrc->getPtrToData(jumpStartAddress);
415                 parsing_printf("%s[%d]: jumpStartPtr (0x%lx) = %p\n", FILE__, __LINE__, jumpStartAddress, jumpStartPtr);
416                 if (jumpStartPtr)
417                     jumpStart = (is64
418                             ? *((Address  *)jumpStartPtr)
419                     : *((uint32_t *)jumpStartPtr));
420                 parsing_printf("%s[%d]: jumpStart 0x%lx, initialAddr 0x%lx\n",
421                                 FILE__, __LINE__, jumpStart, initialAddress);
422                 if (jumpStartPtr == NULL) {
423                     return false;
424                 }
425             }
426             void *tableStartPtr = _isrc->getPtrToData(tableStartAddress);
427             parsing_printf("%s[%d]: tableStartPtr (0x%lx) = %p\n", FILE__, __LINE__, tableStartAddress, tableStartPtr);
428             tableStart = *((Address *)tableStartPtr);
429             if (tableStartPtr)
430                 tableStart = (is64
431                         ? *((Address  *)tableStartPtr)
432                 : *((uint32_t *)tableStartPtr));
433             else {
434                 return false;
435             }
436             parsing_printf("\t... tableStart 0x%lx\n", tableStart);
437
438             bool tableData = false;
439
440             for(int i=0;i<maxSwitch;i++){
441                 Address tableEntry = adjustEntry + tableStart + (i * instruction::size());
442                 parsing_printf("\t\tTable entry at 0x%lx\n", tableEntry);
443                 if (_isrc->isValidAddress(tableEntry)) {
444                     int jumpOffset;
445                     if (tableData) {
446                         jumpOffset = *((int *)_isrc->getPtrToData(tableEntry));
447                     }
448                     else {
449                         jumpOffset = *((int *)_isrc->getPtrToInstruction(tableEntry));
450                     }
451
452                     parsing_printf("\t\t\tjumpOffset 0x%lx\n", jumpOffset);
453                     Address res = (Address)(jumpStart + jumpOffset);
454
455                     if (_isrc->isCode(res)) {
456                         outEdges.push_back(std::make_pair((Address)(jumpStart+jumpOffset), INDIRECT));
457                         parsing_printf("\t\t\tEntry of 0x%lx\n", (Address)(jumpStart + jumpOffset));
458                     }
459                 }
460                 else {
461                     parsing_printf("\t\tAddress not valid!\n");
462                 }
463             }
464     }
465 // No TOC, so we're on Power32 Linux.  Do the ELF thing.
466     else
467     {
468         int entriesAdded = 0;
469         for(int i = 0; i < maxSwitch; i++)
470         {
471             void* ptr = NULL;
472             Address tableEntry = tableStartAddress + i*instruction::size();
473             if(_isrc->isValidAddress(tableEntry))
474             {
475                 ptr = _isrc->getPtrToInstruction(tableEntry);
476             }
477             if(ptr)
478             {
479                 int jumpOffset = *((int *)ptr);
480                 outEdges.push_back(std::make_pair((Address)(jumpStartAddress+jumpOffset), INDIRECT));
481                 parsing_printf("\t\t\t[0x%lx] -> 0x%lx\n", tableEntry, jumpStartAddress+jumpOffset);
482                 ++entriesAdded;
483             }
484         }
485         if(!entriesAdded)
486         {
487             parsing_printf("%s[%d]: no entries added from jump table, returning false\n", FILE__, __LINE__);
488             return false;
489         }
490         parsing_printf("%s[%d]: Found %d entries in jump table, returning success\n", FILE__, __LINE__, entriesAdded);
491     }
492
493 // Sanity check entries in res
494     for (std::vector<std::pair<Address, EdgeTypeEnum> >::iterator iter = outEdges.begin();
495         iter != outEdges.end(); iter++) {
496             if ((iter->first) % 4) {
497                 parsing_printf("Warning: found unaligned jump table destination 0x%lx for jump at 0x%lx, disregarding table\n",
498                                 iter->first, initialAddress);
499                 return false;
500             }
501         }
502         return true;
503 }
504
505
506 Address IA_IAPI::findThunkInBlock(Block* , Address& ) const
507 {
508     return 0;
509 }
510
511
512 std::pair<Address, Address> IA_IAPI::findThunkAndOffset(Block* ) const
513 {
514     return std::make_pair(0, 0);
515 }
516
517 boost::tuple<Instruction::Ptr,
518 Instruction::Ptr,
519 bool> IA_IAPI::findMaxSwitchInsn(Block*) const
520 {
521     return boost::make_tuple(Instruction::Ptr(), Instruction::Ptr(), false);
522 }
523
524 Address IA_IAPI::getTableAddress(Instruction::Ptr, Address,  Address) const
525 {
526     return 0;
527 }
528
529 bool IA_IAPI::fillTableEntries(Address,
530                             Address,
531                             unsigned,
532                             unsigned,
533                             std::vector<std::pair< Address, EdgeTypeEnum> >&) const
534 {
535     return false;
536 }
537
538
539 bool IA_IAPI::computeTableBounds(Instruction::Ptr,
540                                 Instruction::Ptr,
541                                 Instruction::Ptr,
542                                 bool,
543                                 unsigned&,
544                                 unsigned&) const
545 {
546     return false;
547 }
548
549 bool IA_IAPI::isThunk() const {
550     return false;
551 }
552
553 bool IA_IAPI::isTailCall(Function*,unsigned int) const
554 {
555     return false;
556 }
557
558 bool IA_IAPI::savesFP() const
559 {
560     return false;
561 }
562
563 bool IA_IAPI::isStackFramePreamble() const
564 {
565     return false;
566 }
567
568 bool IA_IAPI::cleansStack() const
569 {
570     return false;
571 }
572
573
574 bool IA_IAPI::isReturnAddrSave() const
575 {
576     // FIXME it seems as though isReturnAddrSave won't work for PPC64
577     static RegisterAST::Ptr ppc_theLR(new RegisterAST(ppc32::lr));
578     static RegisterAST::Ptr ppc_stackPtr(new RegisterAST(ppc32::r1));
579     static RegisterAST::Ptr ppc_gpr0(new RegisterAST(ppc32::r0));
580
581     bool foundMFLR = false;   
582     bool ret = false;
583     Instruction::Ptr ci = curInsn();
584     if(ci->getOperation().getID() == power_op_mfspr &&
585        ci->isRead(ppc_theLR) &&
586        ci->isWritten(ppc_gpr0))
587     {
588         foundMFLR = true;
589     }
590
591     if(!foundMFLR)
592         return false;
593
594     // walk to first control flow transfer instruction, looking
595     // for a save of gpr0
596     int cnt = 1;
597     IA_IAPI copy(dec,getAddr(),_obj,_cr,_isrc);
598     while(!copy.hasCFT() && copy.curInsn()) {
599         ci = copy.curInsn();
600         if(ci->writesMemory() &&
601            ci->isRead(ppc_stackPtr) &&
602            ci->isRead(ppc_gpr0))
603         {
604             ret = true;
605             break;
606         }
607         copy.advance();
608         ++cnt;
609     }
610     parsing_printf("[%s:%d] isReturnAddrSave examined %d instructions\n",   
611         FILE__,__LINE__,cnt);
612     return ret;
613 }
614
615 bool IA_IAPI::isFakeCall() const
616 {
617     return false;
618 }
619
620 bool IA_IAPI::isIATcall() const
621 {
622     return false;
623 }
624
625 static ParseAPI::StackTamper 
626 IA_IAPI::tampersStack(ParseAPI::Function *, Address &) const
627 {
628     return TAMPER_NONE;
629 }