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