1. Enables new jump table analysis for powerpc 2. Fix various inconsistency between...
[dyninst.git] / parseAPI / src / IA_powerDetails.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 "IA_powerDetails.h"
32 #include "Visitor.h"
33 #include "Register.h"
34 #include "Dereference.h"
35 #include "Immediate.h"
36 #include "BinaryFunction.h"
37 #include "debug_parse.h"
38 #include <deque>
39 #include <boost/bind.hpp>
40 #include <algorithm>
41 #include <iterator>
42 #include <boost/iterator/indirect_iterator.hpp>
43
44 #include "IndirectAnalyzer.h"
45
46
47 using namespace Dyninst;
48 using namespace InstructionAPI;
49 using namespace Dyninst::InsnAdapter;
50 using namespace Dyninst::ParseAPI;
51
52
53 namespace Dyninst
54 {
55     namespace InsnAdapter
56     {
57         namespace detail
58         {
59             class TOCandOffsetExtractor : public Dyninst::InstructionAPI::Visitor
60             {
61             public:
62                 TOCandOffsetExtractor(Address TOCvalue) : result(0), toc_contents(TOCvalue) {}
63                 virtual ~TOCandOffsetExtractor() {}
64                 virtual void visit(BinaryFunction* b) {
65                     Address arg1 = m_stack.front();
66                     m_stack.pop_front();
67                     Address arg2 = m_stack.front();
68                     m_stack.pop_front();
69                     if(b->isAdd()) {
70                         result = arg1 + arg2;
71                     } else if(b->isMultiply()) {
72                         result = arg1 * arg2;
73                     } else {
74                         assert(!"unexpected binary function!");
75                         result = 0;
76                     }
77                     parsing_printf("\tTOC visitor visiting binary function, result is 0x%lx\n",
78                                    result);
79                     m_stack.push_front(result);
80                 }
81                 virtual void visit(Immediate* i) {
82                     Address tmp = i->eval().convert<Address>();
83                     result = tmp;
84                     parsing_printf("\tTOC visitor visiting immediate, result is 0x%lx\n",
85                                    result);
86                     m_stack.push_front(tmp);
87                 }
88                 virtual void visit(RegisterAST* r) {
89                     if(r->getID() == toc_reg->getID()) {
90                         m_stack.push_front(toc_contents);
91                     } else {
92                         m_stack.push_front(0);
93                     }
94                     result = m_stack.front();
95                     parsing_printf("\tTOC visitor visiting register, result is 0x%lx\n",
96                                    result);
97                 }
98                 virtual void visit(Dereference*) {}
99                 void clear() {
100                     m_stack.clear();
101                     result = 0;
102                 }
103                 std::deque<Address> m_stack;
104                 Address result;
105                 Address toc_contents;
106                 RegisterAST::Ptr toc_reg;
107             };
108         }
109     }
110 };
111
112
113 bool IA_powerDetails::findTableAddrNoTOC(const IA_IAPI* blockToCheck)
114 {
115     std::set<RegisterAST::Ptr> regs;
116     std::set<RegisterAST::Ptr> writeregs, readregs;
117     RegisterAST::Ptr writereg, readreg;
118     int dfgreg;
119     std::set<RegisterAST::Ptr>::iterator itw, itr;
120     std::set<int>::iterator itd;
121     toc_visitor->clear();
122     bool foundAddis = false;
123     bool foundAddi = false;
124     bool foundDep = false;
125     while(patternIter != blockToCheck->allInsns.begin())
126     {
127         patternIter--;
128         // Do backward dataflow analysis to match the registers that compute the jump table address
129         parsing_printf("\tchecking insn %s at 0x%lx\n", patternIter->second->format().c_str(),
130                        patternIter->first);
131         // Ignore rlwinm instruction since its used for the index and not the table start.
132         // Also, remove it from the backwards DFG
133         if(patternIter->second->getOperation().getID() == power_op_rlwinm){
134             patternIter->second->getWriteSet(writeregs);
135             for(itw=writeregs.begin(); itw!= writeregs.end(); itw++){
136                 writereg=*(itw);
137                 for(itd=dfgregs.begin(); itd!= dfgregs.end(); itd++){
138                     dfgreg = *itd;
139                     if (writereg->getID() == dfgreg) {
140                         parsing_printf("found Match - erasing rlwinm  \n");
141                         dfgregs.erase(*itd);
142                     }
143                 }
144             }
145             continue;
146         }
147
148         writeregs.clear();
149         patternIter->second->getWriteSet(writeregs);
150         foundDep =false;
151
152         for(itw=writeregs.begin(); itw!= writeregs.end(); itw++){
153             writereg=*(itw);
154             parsing_printf("Register Written %s \n", writereg->format().c_str());
155             for(itd=dfgregs.begin(); itd!= dfgregs.end(); itd++){
156                 dfgreg = *itd;
157                 parsing_printf("DFG has %d \n", dfgreg);
158                 if (writereg->getID() == dfgreg) {
159                     parsing_printf("found Match \n");
160                     dfgregs.erase(*itd);
161                     readregs.clear();
162                     patternIter->second->getReadSet(readregs);
163                     for(itr=readregs.begin(); itr!= readregs.end(); itr++){
164                         readreg=*(itr);
165                         dfgregs.insert(readreg->getID());
166                         parsing_printf("Reading %s \n", readreg->format().c_str());
167                     }
168                     foundDep = true;
169                     break;
170                 }
171             }
172         }
173         // We look for addi-addis combination.
174         // These instruction can occur in any order and in any block before the indirect branch.
175         // Also, there may be more than one addi instruction.
176         // Hence, we use adjustTableStartAddress to keep track of immediate values from addi instructions.
177         if(foundDep && !foundAddis &&
178            (patternIter->second->getOperation().getID() == power_op_addi ||
179             patternIter->second->getOperation().getID() == power_op_addic))
180         {
181             std::set<RegisterAST::Ptr> tmpregs;
182             patternIter->second->getReadSet(tmpregs);
183             if(tmpregs.size() != 1) {
184                 continue;
185             }
186             regs.clear();
187             patternIter->second->getReadSet(regs);
188             if(regs.size() != 1) {
189                 continue;
190             }
191             parsing_printf("\tfound 0x%lx: %s, checking for addis previous\n",
192                            patternIter->first,
193                            patternIter->second->format().c_str());
194             foundAddi = true;
195             toc_visitor->clear();
196             patternIter->second->getOperand(2).getValue()->apply(toc_visitor.get());
197             adjustTableStartAddress += toc_visitor->result;
198         }
199         else if(foundDep && !foundAddi && patternIter->second->getOperation().getID() == power_op_addis)
200         {
201             std::set<RegisterAST::Ptr> tmpregs;
202             patternIter->second->getReadSet(tmpregs);
203             if(tmpregs.size() != 1) {
204                 continue;
205             }
206             regs.clear();
207             patternIter->second->getReadSet(regs);
208             if(regs.size() != 1) {
209                 continue;
210             }
211             parsing_printf("\tfound 0x%lx: %s, checking for addi previous\n",
212                            patternIter->first,
213                            patternIter->second->format().c_str());
214             foundAddis = true;
215             toc_visitor->clear();
216             patternIter->second->getOperand(2).getValue()->apply(toc_visitor.get());
217             tableStartAddress = toc_visitor->result;
218             tableStartAddress *= 10000;
219             tableStartAddress &= 0xFFFF0000;
220
221         } else if( foundDep && foundAddi &&
222                    patternIter->second &&
223                    (patternIter->second->getOperation().getID() == power_op_addis) &&
224                    patternIter->second->isWritten(*(regs.begin())))
225         {
226             foundAddis = true;
227             parsing_printf("\tfound 0x%lx: %s, setting tableStartAddress\n",
228                            patternIter->first,
229                            patternIter->second->format().c_str());
230             toc_visitor->clear();
231             patternIter->second->getOperand(2).getValue()->apply(toc_visitor.get());
232             tableStartAddress += (toc_visitor->result * 0x10000) & 0xFFFF0000;
233             parsing_printf("\ttableStartAddress = 0x%lx\n",
234                            tableStartAddress);
235             break;
236         } else if( foundDep && foundAddis &&
237                    patternIter->second &&
238                    ((patternIter->second->getOperation().getID() == power_op_addi) ||
239                     (patternIter->second->getOperation().getID() == power_op_addic)) &&
240                    patternIter->second->isWritten(*(regs.begin())))
241         {
242             foundAddi = true;
243             parsing_printf("\tfound 0x%lx: %s, setting tableStartAddress\n",
244                            patternIter->first,
245                            patternIter->second->format().c_str());
246             toc_visitor->clear();
247             patternIter->second->getOperand(2).getValue()->apply(toc_visitor.get());
248             tableStartAddress += toc_visitor->result;
249             parsing_printf("\ttableStartAddress = 0x%lx\n", tableStartAddress);
250             break;
251         }
252     }
253     if (!foundAddi || !foundAddis)
254         tableStartAddress = 0;
255     else
256         tableStartAddress += adjustTableStartAddress;
257
258     parsing_printf(" TABLE START 0x%lx 0x%lx %ld\n", tableStartAddress, adjustTableStartAddress, adjustTableStartAddress);
259
260     // If we've found an addi/addis combination and it's a relative table, look for a mfspr/thunk combination that
261     // feeds that...
262     if(tableStartAddress && tableIsRelative)
263     {
264         parsing_printf("\ttableStartAddress non-zero, tableIsRelative true\n");
265         bool foundThunk = false;
266         bool foundMFSPR = false;
267         Address GOTaddress = 0;
268         while(patternIter != blockToCheck->allInsns.begin())
269         {
270             patternIter--;
271             if(patternIter->second->getOperation().getID() == power_op_mfspr &&
272                patternIter->second->isWritten(*(regs.begin())))
273             {
274                 foundMFSPR = true;
275                 break;
276             }
277         }
278         while(patternIter != blockToCheck->allInsns.begin())
279         {
280             patternIter--;
281             if(patternIter->second->getCategory() == c_CallInsn) // mid-block call, must be a thunk
282             {
283                 patternIter++;
284                 parsing_printf("\tfound thunk/mfspr combo, adjusting tableStartAddress by 0x%lx\n", patternIter->first);
285                 GOTaddress = tableStartAddress + patternIter->first;
286                 foundThunk = true;
287                 break;
288             }
289         }
290         if(foundThunk && foundMFSPR)
291         {
292             toc_visitor->toc_reg = *(regs.begin());
293             toc_reg = toc_visitor->toc_reg;
294             toc_visitor->toc_contents = GOTaddress;
295             tableStartAddress = 0;
296             patternIter = currentBlock->curInsnIter;
297             parsing_printf("\t calling parseRelativeTableIdiom with toc_reg %s\n", toc_visitor->toc_reg->format().c_str());
298             return parseRelativeTableIdiom();
299         }
300     }
301     else
302     {
303         parsing_printf("\ttableStartAddress = 0x%lx, tableIsRelative = %s\n", tableStartAddress,
304                        tableIsRelative ? "true" : "false");
305     }
306     return tableStartAddress == 0;
307 }
308
309 bool IA_powerDetails::parseRelativeTableIdiom()
310 {
311     bool foundAddress = false;
312     while(patternIter != currentBlock->allInsns.begin())
313     {
314         patternIter--;
315         parsing_printf("\t checking 0x%lx: %s for lwz/ld\n", patternIter->first, patternIter->second->format().c_str());
316         if((patternIter->second->getOperation().getID() == power_op_lwz ||
317             patternIter->second->getOperation().getID() == power_op_ld) &&
318            patternIter->second->isRead(toc_reg))
319         {
320             toc_visitor->clear();
321             patternIter->second->getOperand(1).getValue()->apply(toc_visitor.get());
322             parsing_printf("%s[%d]: setting jumpStartAddress to 0x%lx, insn %s, TOC 0x%lx\n", FILE__, __LINE__,
323                            toc_visitor->result, patternIter->second->format().c_str(), toc_visitor->toc_contents);
324             jumpStartAddress = toc_visitor->result;
325             foundAddress = true;
326             tableStartAddress = jumpStartAddress;
327             adjustEntry = 0;
328             break;
329         }
330     }
331     if(patternIter == currentBlock->allInsns.begin())
332     {
333         if (foundAddress) {
334             return true;
335         } else {
336
337             // If we've already backed up to the beginning, we're not going to find a legit table
338             // start address; bail now.
339             parsing_printf("%s[%d]: jumpStartAddress insn was first in block w/relative table, ret false\n",
340                            FILE__, __LINE__);
341             return false;
342         }
343     }
344     // Anyone know what this does?
345     patternIter--;
346     if((patternIter->second->getOperation().getID() == power_op_lwz ||
347         patternIter->second->getOperation().getID() == power_op_ld))
348     {
349         toc_visitor->clear();
350         patternIter->second->getOperand(1).getValue()->apply(toc_visitor.get());
351         adjustEntry = toc_visitor->result;
352         foundAdjustEntry = true;
353         parsing_printf("%s[%d]: setting adjustEntry to 0x%lx, insn %s, TOC 0x%lx\n", FILE__, __LINE__,
354                        toc_visitor->result, patternIter->second->format().c_str(), toc_visitor->toc_contents);
355     }
356
357     while(patternIter != currentBlock->allInsns.begin()){
358         patternIter--;
359         if((patternIter->second->getOperation().getID() == power_op_lwz ||
360             patternIter->second->getOperation().getID() == power_op_ld) &&
361            patternIter->second->isRead(toc_reg))
362         {
363             toc_visitor->clear();
364             patternIter->second->getOperand(1).getValue()->apply(toc_visitor.get());
365             tableStartAddress = toc_visitor->result;
366             parsing_printf("%s[%d]: setting tableStartAddress to 0x%lx, insn %s, TOC 0x%lx\n", FILE__, __LINE__,
367                            toc_visitor->result, patternIter->second->format().c_str(), toc_visitor->toc_contents);
368             break;
369         }
370     }
371     return true;
372 }
373
374 namespace detail_ppc
375 {
376     bool isNonCallEdge(ParseAPI::Edge* e)
377     {
378         return e->type() != CALL;
379     }
380     bool leadsToVisitedBlock(ParseAPI::Edge* e, const std::set<Block*>& visited)
381     {
382         Block* src = e->src();
383         return visited.find(src) != visited.end();
384     }
385     void processPredecessor(ParseAPI::Edge* e, std::set<Block*>& visited, std::deque<Block*>& worklist)
386     {
387         parsing_printf("\t\tblock %x, edge type %s\n",
388                        e->src()->start(),
389                        format(e->type()).c_str());
390
391         // FIXME debugging assert
392         assert(isNonCallEdge(e));
393
394         // FIXME check this algorithm... O(log n) lookup in visited
395         if(!leadsToVisitedBlock(e, visited))
396         {
397             worklist.push_back(e->src());
398             visited.insert(e->src());
399         }
400     }
401 };
402
403 bool IA_powerDetails::scanForAdjustOrBase(IA_IAPI::allInsns_t::const_iterator start,
404                                           IA_IAPI::allInsns_t::const_iterator end,
405                                           RegisterAST::Ptr &jumpAddrReg) {
406     std::set<RegisterAST::Ptr> scratchRegs;
407     std::set<RegisterAST::Ptr> loadRegs;
408     loadRegs.insert(jumpAddrReg);
409     for (; start != end; --start) {
410         InstructionAPI::Instruction::Ptr insn = start->second;
411         parsing_printf("\t\t Examining 0x%lx / %s\n",
412                        start->first, start->second->format().c_str());
413
414         if ((insn->getOperation().getID() == power_op_ld ||
415              insn->getOperation().getID() == power_op_ldx) &&
416             insn->isWritten(jumpAddrReg)) {
417             scratchRegs.clear();
418             insn->getReadSet(scratchRegs);
419             loadRegs.insert(scratchRegs.begin(), scratchRegs.end());
420             parsing_printf("Found a load; now have %d load regs\n", loadRegs.size());
421         }
422         else if(insn->getOperation().getID() == power_op_addi &&
423                 !foundAdjustEntry) {
424             parsing_printf("Found add immediate (%d load regs)...\n", loadRegs.size());
425             scratchRegs.clear();
426             insn->getWriteSet(scratchRegs);
427
428             bool found = false;
429             // This is apparently broken
430             for (std::set<RegisterAST::Ptr>::iterator iter = loadRegs.begin(); iter != loadRegs.end(); ++iter) {
431                 RegisterAST *tmp = (*iter).get();
432                 RegisterAST *cmp = (*(scratchRegs.begin())).get();
433                 if (*tmp == *cmp) {
434                     found = true;
435                     break;
436                 }
437             }
438             if (!found) continue;
439
440             parsing_printf("... that adds to a load reg\n");
441             foundAdjustEntry = true;
442             toc_visitor->clear();
443             parsing_printf("... with operand %s\n", insn->getOperand(1).format(insn->getArch(), start->first).c_str());
444             insn->getOperand(1).getValue()->apply(toc_visitor.get());
445             adjustEntry = toc_visitor->result;
446             if (!adjustEntry)
447                 insn->getOperand(2).getValue()->apply(toc_visitor.get());
448             adjustEntry = toc_visitor->result;
449         }
450         else if((insn->getOperation().getID() == power_op_lwz ||
451                  insn->getOperation().getID() == power_op_ld) &&
452                 insn->isRead(toc_reg) &&
453                 insn->isWritten(jumpAddrReg))
454         {
455             parsing_printf("\t found TOC load at %s\n", insn->format().c_str());
456             toc_visitor->clear();
457             insn->getOperand(1).getValue()->apply(toc_visitor.get());
458             tableStartAddress = toc_visitor->result;
459             break;
460         }
461     }
462     return true;
463 }
464
465 // Like the above, but a wider net
466 bool IA_powerDetails::findTableBase(IA_IAPI::allInsns_t::const_iterator start,
467                                     IA_IAPI::allInsns_t::const_iterator end) {
468     for (; start != end; --start) {
469         if(!start->second) continue;
470         parsing_printf("\t\t Examining 0x%lx / %s\n",
471                        start->first, start->second->format().c_str());
472         if((start->second->getOperation().getID() == power_op_lwz ||
473             start->second->getOperation().getID() == power_op_ld) &&
474            start->second->isRead(toc_reg)) {
475             parsing_printf("\t found TOC load at %s\n", start->second->format().c_str());
476             toc_visitor->clear();
477             start->second->getOperand(1).getValue()->apply(toc_visitor.get());
478             tableStartAddress = toc_visitor->result;
479             break;
480         }
481     }
482     return true;
483 }
484
485 bool IA_powerDetails::parseJumpTable(Function * currFunc,
486                                      Block* currBlk,
487                                      std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges)
488 {
489     IndirectControlFlowAnalyzer icfa(currFunc, currBlk);
490     bool ret = icfa.NewJumpTableAnalysis(outEdges);
491
492     parsing_printf("Jump table parser returned %d, %d edges\n", ret, outEdges.size());
493     for (auto oit = outEdges.begin(); oit != outEdges.end(); ++oit) parsing_printf("edge target at %lx\n", oit->first);
494     // Update statistics 
495     currBlk->obj()->cs()->incrementCounter(PARSE_JUMPTABLE_COUNT);
496     if (!ret) currBlk->obj()->cs()->incrementCounter(PARSE_JUMPTABLE_FAIL);
497
498     return ret;
499 }
500
501
502
503 // This should only be called on a known indirect branch...
504 bool IA_powerDetails::parseJumpTable(Block* currBlk,
505                                      std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges)
506 {
507
508     Address initialAddress = currentBlock->current;
509     toc_reg.reset(new RegisterAST(ppc32::r2));
510
511     TOC_address = currentBlock->_obj->cs()->getTOC();
512     toc_visitor.reset(new detail::TOCandOffsetExtractor(TOC_address));
513     toc_visitor->toc_reg = toc_reg;
514
515     // If there are no prior instructions then we can't be looking at a
516     // jump through a jump table.
517     if(currentBlock->allInsns.size() < 2) {
518         parsing_printf("%s[%d]: allInsns.size() == %d, ret false", FILE__, __LINE__, currentBlock->allInsns.size());
519         return false;
520     }
521
522
523     // Check if the previous instruction is a move to CTR or LR;
524     // if it is, then this is the pattern we're familiar with.  The
525     // register being moved into CTR or LR has the address to jump to.
526     patternIter = currentBlock->curInsnIter;
527     patternIter--;
528     RegisterAST::Ptr jumpAddrReg;
529     std::set<RegisterAST::Ptr> regs;
530     if(patternIter->second->getOperation().getID() == power_op_mtspr)
531     {
532         regs.clear();
533         patternIter->second->getReadSet(regs);
534         if(regs.size() != 1) {
535             parsing_printf("expected mtspr to read 1 register, insn is %s\n", patternIter->second->format().c_str());
536             return false;
537         }
538         jumpAddrReg = *(regs.begin());
539         parsing_printf("%s[%d]: JUMPREG %s mtspr at prev insn %s \n", FILE__, __LINE__, jumpAddrReg->format().c_str(), patternIter->second->format().c_str());
540         dfgregs.insert(jumpAddrReg->getID());
541     }
542     else
543     {
544         parsing_printf("%s[%d]: couldn't find mtspr at prev insn %s, ret false", FILE__, __LINE__,
545                        patternIter->second->format().c_str());
546         return false;
547     }
548     assert(jumpAddrReg);
549     // In the pattern we've seen, if the instruction previous to this is
550     // an add with a result that ends up being used as the jump address,
551     // then we're adding a relative value we got from the table to a base
552     // address to get the jump address; in other words, the contents of
553     // the jump table are relative.
554     tableIsRelative = false;
555     if(patternIter != currentBlock->allInsns.begin())
556     {
557         patternIter--;
558         if(patternIter->second->getOperation().getID() == power_op_add &&
559            patternIter->second->isWritten(*(regs.begin())))
560         {
561             tableIsRelative = true;
562         }
563     }
564     parsing_printf(" TableIsRelative %d\n", tableIsRelative);
565
566     patternIter = currentBlock->curInsnIter;
567
568     jumpStartAddress = 0;
569     adjustEntry = 0;
570     tableStartAddress = 0;
571     adjustTableStartAddress = 0;
572     foundAdjustEntry = false;
573
574     parsing_printf("\t TOC_address 0x%lx\n", TOC_address);
575     if(!TOC_address)
576     {
577         // Find addi-addis instructions to determine the jump table start address.
578         // These instructions can be anywhere in the function before the
579         // indirect jump.Hence parse through the current block and previous block
580         // till we reach the function entry.
581         Block* worklistBlock = currBlk;
582         std::set <Block*> visited;
583         std::deque<Block*> worklist;
584         worklist.insert(worklist.begin(), worklistBlock);
585         visited.insert(worklistBlock);
586         Intraproc epred;
587         parsing_printf("Looking for table start address over blocks to function entry\n");
588         while(!worklist.empty())
589         {
590             worklistBlock= worklist.front();
591             worklist.pop_front();
592             parsing_printf("\tAddress low 0x%lx high 0x%lx current block 0x%lx low 0x%lx high 0x%lx \n", worklistBlock->low(), worklistBlock->high(), currentBlock->current, currBlk->low(), currBlk->high());
593             Address blockStart = worklistBlock->start();
594             const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
595             parsing_printf(" Block start 0x%lx \n", blockStart);
596             InstructionDecoder dec(b, worklistBlock->size(), currentBlock->_isrc->getArch());
597             IA_IAPI IABlock(dec, blockStart, currentBlock->_obj, currentBlock->_cr, currentBlock->_isrc, worklistBlock);
598
599             while(IABlock.getInstruction() && !IABlock.hasCFT()) {
600                 IABlock.advance();
601             }
602
603             patternIter = IABlock.curInsnIter;
604             findTableAddrNoTOC(&IABlock);
605             if(!jumpStartAddress)
606             {
607                 jumpStartAddress = tableStartAddress;
608             }
609             if (tableStartAddress != 0) {
610                 jumpStartAddress = tableStartAddress;
611                 parsing_printf("\t\tjumpStartAddress 0x%lx \n", jumpStartAddress);
612                 break;
613             }
614             std::for_each(boost::make_filter_iterator(epred, worklistBlock->sources().begin(), worklistBlock->sources().end()),
615                           boost::make_filter_iterator(epred, worklistBlock->sources().end(), worklistBlock->sources().end()),
616                           boost::bind(detail_ppc::processPredecessor, _1, boost::ref(visited), boost::ref(worklist)));
617
618         }
619
620     }
621     else if (tableIsRelative) {
622         if(!parseRelativeTableIdiom())
623         {
624             return false;
625         }
626     } else {
627         parsing_printf("\t Table is not relative and we know the TOC is 0x%lx, searching for table base\n",
628                        TOC_address);
629         foundAdjustEntry = false;
630
631         scanForAdjustOrBase(patternIter, currentBlock->allInsns.begin(), jumpAddrReg);
632
633         if (!tableStartAddress) {
634             // Keep looking in the immediate predecessor - XLC
635             for (Block::edgelist::const_iterator e_iter = currBlk->sources().begin();
636                  e_iter != currBlk->sources().end(); ++e_iter) {
637                 Address blockStart = (*e_iter)->src()->start();
638                 const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
639                 InstructionDecoder dec(b, (*e_iter)->src()->size(), currentBlock->_isrc->getArch());
640                 IA_IAPI IABlock(dec, blockStart, currentBlock->_obj, currentBlock->_cr, currentBlock->_isrc, (*e_iter)->src());
641
642                 // Cache instructions
643                 while(IABlock.getInstruction() && !IABlock.hasCFT()) {
644                     IABlock.advance();
645                 }
646
647                 IA_IAPI::allInsns_t::const_iterator localIter = IABlock.curInsnIter;
648                 findTableBase(localIter, IABlock.allInsns.begin());
649             }
650         }
651     }
652
653     const Block::edgelist & sourceEdges = currBlk->sources();
654     if(sourceEdges.size() != 1 || (*sourceEdges.begin())->type() == CALL) {
655         parsing_printf("%s[%d]: jump table not properly guarded, ret false\n", FILE__, __LINE__);
656         return false;
657     }
658
659
660
661     // We could also set this = jumpStartAddress...
662     if (tableStartAddress == 0)  {
663         parsing_printf("%s[%d]: couldn't find table start addr, ret false\n", FILE__, __LINE__);
664         return false;
665
666     }
667
668     parsing_printf("%s[%d]: table start addr is 0x%x\n", FILE__, __LINE__, tableStartAddress);
669     int maxSwitch = 0;
670
671     Block* sourceBlock = (*sourceEdges.begin())->src();
672     Address blockStart = sourceBlock->start();
673     const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
674     InstructionDecoder dec(b, sourceBlock->size(), currentBlock->_isrc->getArch());
675     IA_IAPI prevBlock(dec, blockStart,currentBlock->_obj,currentBlock->_cr,currentBlock->_isrc, sourceBlock);
676     while(!prevBlock.hasCFT() && prevBlock.getInstruction()) {
677         prevBlock.advance();
678     }
679
680     parsing_printf("%s[%d]: checking for max switch...\n", FILE__, __LINE__);
681     bool foundBranch = false;
682     IA_IAPI::allInsns_t::reverse_iterator iter;
683     for(iter = prevBlock.allInsns.rbegin(); iter != prevBlock.allInsns.rend(); iter++)
684
685     {
686         parsing_printf("\t\tchecking insn 0x%x: %s for cond branch + compare\n", iter->first,
687                        iter->second->format().c_str());
688         if(iter->second->getOperation().getID() == power_op_bc) // make this a true cond. branch check
689         {
690             foundBranch = true;
691         } else if(foundBranch &&
692                   (iter->second->getOperation().getID() == power_op_cmpi ||
693                    iter->second->getOperation().getID() == power_op_cmpli))
694         {
695             maxSwitch = iter->second->getOperand(2).getValue()->eval().convert<int>() + 1;
696             break;
697
698         }
699     }
700
701     parsing_printf("%s[%d]: After checking: max switch %d\n", FILE__, __LINE__, maxSwitch);
702     if(!maxSwitch){
703         return false;
704     }
705
706     Address jumpStart = 0;
707     Address tableStart = 0;
708     bool is64 = (currentBlock->_isrc->getAddressWidth() == 8);
709     std::vector<std::pair< Address, EdgeTypeEnum> > edges;
710
711     if(TOC_address)
712     {
713         if (tableIsRelative) {
714             void *jumpStartPtr = currentBlock->_isrc->getPtrToData(jumpStartAddress);
715             parsing_printf("%s[%d]: jumpStartPtr (0x%lx) = %p\n", FILE__, __LINE__, jumpStartAddress, jumpStartPtr);
716             if (jumpStartPtr)
717                 jumpStart = (is64
718                              ? *((Address  *)jumpStartPtr)
719                              : *((uint32_t *)jumpStartPtr));
720             parsing_printf("%s[%d]: jumpStart 0x%lx, initialAddr 0x%lx\n",
721                            FILE__, __LINE__, jumpStart, initialAddress);
722             if (jumpStartPtr == NULL) {
723                 return false;
724             }
725         }
726         void *tableStartPtr = currentBlock->_isrc->getPtrToData(tableStartAddress);
727         parsing_printf("%s[%d]: tableStartPtr (0x%lx) = %p\n", FILE__, __LINE__, tableStartAddress, tableStartPtr);
728         tableStart = *((Address *)tableStartPtr);
729         if (tableStartPtr)
730             tableStart = (is64
731                           ? *((Address  *)tableStartPtr)
732                           : *((uint32_t *)tableStartPtr));
733         else {
734             return false;
735         }
736         parsing_printf("\t... tableStart 0x%lx\n", tableStart);
737
738         bool tableData = false;
739         for(int i=0;i<maxSwitch;i++){
740             Address tableEntry = adjustEntry + tableStart + (i * 4 /*instruction::size()*/);
741             parsing_printf("\t\tTable entry at 0x%lx\n", tableEntry);
742             if (currentBlock->_isrc->isValidAddress(tableEntry)) {
743                 int jumpOffset;
744                 if (tableData) {
745                     jumpOffset = *((int *)currentBlock->_isrc->getPtrToData(tableEntry));
746                 }
747                 else {
748                     jumpOffset = *((int *)currentBlock->_isrc->getPtrToInstruction(tableEntry));
749                 }
750
751                 parsing_printf("\t\t\tjumpOffset 0x%lx\n", jumpOffset);
752                 Address res = (Address)(jumpStart + jumpOffset);
753
754                 if (currentBlock->_isrc->isCode(res)) {
755                     edges.push_back(std::make_pair((Address)(jumpStart+jumpOffset), INDIRECT));
756                     parsing_printf("\t\t\tEntry of 0x%lx\n", (Address)(jumpStart + jumpOffset));
757                 }
758             }
759             else {
760                 parsing_printf("\t\tAddress not valid!\n");
761             }
762         }
763     }
764         // No TOC, so we're on Power32 Linux.  Do the ELF thing.
765     else
766     {
767         jumpStart = jumpStartAddress;
768         tableStart = tableStartAddress;
769         parsing_printf(" jumpStartaddress 0x%lx tableStartAddress 0x%lx \n", jumpStartAddress, tableStartAddress);
770         if(toc_visitor->toc_contents)
771         {
772             void* tmp = NULL;
773             if(currentBlock->_isrc->isValidAddress(jumpStartAddress))
774             {
775                 tmp = currentBlock->_isrc->getPtrToData(jumpStartAddress);
776                 if(!tmp)
777                 {
778                     tmp = currentBlock->_isrc->getPtrToInstruction(jumpStartAddress);
779                 }
780                 if(tmp)
781                 {
782                     jumpStart = *((Address*)tmp);
783                     parsing_printf("\t\tjumpStart adjusted to 0x%lx\n", jumpStart);
784                 }
785             }
786             if(currentBlock->_isrc->isValidAddress(tableStartAddress))
787             {
788                 tmp = currentBlock->_isrc->getPtrToData(tableStartAddress);
789                 if(!tmp)
790                 {
791                     tmp = currentBlock->_isrc->getPtrToInstruction(tableStartAddress);
792                 }
793                 if(tmp)
794                 {
795                     tableStart = *((Address*)tmp);
796                     parsing_printf("\t\ttableStart adjusted to 0x%lx\n", jumpStart);
797                 }
798             }
799         }
800
801
802         if (jumpStart == 0) {
803 #if defined(WITH_SYMTAB_API)
804             // If jump table address is a relocation entry, this will be filled by the loader
805             // This case is common in shared library where the table address is in the GOT section which is filled by the loader
806             // Find the relocation entry for this address and look up its value
807
808             Block* sourceBlock = (*sourceEdges.begin())->src();
809             Address blockStart = sourceBlock->start();
810             const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
811             InstructionDecoder dec(b, sourceBlock->size(), currentBlock->_isrc->getArch());
812             IA_IAPI IABlock(dec, blockStart,currentBlock->_obj,currentBlock->_cr,currentBlock->_isrc, sourceBlock);
813
814             SymtabCodeSource *scs = dynamic_cast<SymtabCodeSource *>(IABlock._obj->cs());
815             SymtabAPI::Symtab * symtab = scs->getSymtabObject();
816             std::vector<SymtabAPI::Region *> regions;
817             symtab->getAllRegions(regions);
818             for (unsigned index = 0 ; index < regions.size(); index++) {
819                 if (regions[index]->getRegionType() == SymtabAPI::Region::RT_RELA ||
820                     regions[index]->getRegionType() == SymtabAPI::Region::RT_REL) {
821                     std::vector<SymtabAPI::relocationEntry> relocs =
822                             regions[index]->getRelocations();
823                     parsing_printf(" \t\trelocation size %d looking for 0x%lx\n", relocs.size(), jumpStartAddress);
824                     for (unsigned i = 0; i < relocs.size(); ++i) {
825                         parsing_printf(" \t 0x%lx => 0x%lx addend 0x%lx \n", relocs[i].rel_addr(),relocs[i].target_addr(), relocs[i].addend());
826                         if (relocs[i].rel_addr() == jumpStartAddress) {
827                             jumpStart = relocs[i].addend();
828                             break;
829                         }
830                     }
831                     break;
832                 }
833             }
834 #else
835             // Can't parse relocation entries without Symtab
836         return false;
837 #endif
838         }
839         if (tableStart == 0) tableStart = jumpStart;
840
841         if (!tableIsRelative) {
842             jumpStart = 0;
843         }
844         parsing_printf(" jumpStartaddress 0x%lx tableStartAddress 0x%lx \n", jumpStart, tableStart);
845
846         int entriesAdded = 0;
847         for(int i = 0; i < maxSwitch; i++)
848         {
849             void* ptr = NULL;
850             Address tableEntry = tableStart + i*4; // instruction::size();
851             if(currentBlock->_isrc->isValidAddress(tableEntry))
852             {
853                 ptr = currentBlock->_isrc->getPtrToInstruction(tableEntry);
854             }
855             if(ptr)
856             {
857                 int jumpOffset = *((int *)ptr);
858                 edges.push_back(std::make_pair((Address)(jumpStart+jumpOffset), INDIRECT));
859                 parsing_printf("\t\t\t[0x%lx] -> 0x%lx (0x%lx in table)\n", tableEntry,
860                                jumpStart+jumpOffset,
861                                jumpOffset);
862                 ++entriesAdded;
863             }
864             else
865             {
866                 parsing_printf("\t\t\t[0x%lx] -> [INVALID]\n", tableEntry);
867             }
868         }
869         if(!entriesAdded)
870         {
871             parsing_printf("%s[%d]: no entries added from jump table, returning false\n", FILE__, __LINE__);
872             return false;
873         }
874         parsing_printf("%s[%d]: Found %d entries in jump table, returning success\n", FILE__, __LINE__, entriesAdded);
875     }
876
877     // Sanity check entries in res
878     for (std::vector<std::pair<Address, EdgeTypeEnum> >::iterator iter = edges.begin();
879          iter != edges.end(); iter++) {
880         if ((iter->first) % 4) {
881             parsing_printf("Warning: found unaligned jump table destination 0x%lx for jump at 0x%lx, disregarding table\n",
882                            iter->first, initialAddress);
883             return false;
884         }
885     }
886     // If we have found a jump table, add the targets to outEdges
887     for (std::vector<std::pair<Address, EdgeTypeEnum> >::iterator iter = edges.begin();
888          iter != edges.end(); iter++) {
889         parsing_printf("Adding out edge %d/0x%lx\n", iter->second, iter->first);
890         outEdges.push_back(*iter);
891     }
892     return true;
893 }