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