Fix crash when walking backward through blocks ending in fallthrough edges only
[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         if(!start->second) continue;
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     std::set<RegisterAST::Ptr> regs;
519     if(patternIter->second->getOperation().getID() == power_op_mtspr)
520     {
521         regs.clear();
522         patternIter->second->getReadSet(regs);
523         if(regs.size() != 1) {
524             parsing_printf("expected mtspr to read 1 register, insn is %s\n", patternIter->second->format().c_str());
525             return false;
526         }
527         jumpAddrReg = *(regs.begin());
528         parsing_printf("%s[%d]: JUMPREG %s mtspr at prev insn %s \n", FILE__, __LINE__, jumpAddrReg->format().c_str(), patternIter->second->format().c_str());
529         dfgregs.insert(jumpAddrReg->getID());
530     }
531     else
532     {
533         parsing_printf("%s[%d]: couldn't find mtspr at prev insn %s, ret false", FILE__, __LINE__,
534                        patternIter->second->format().c_str());
535         return false;
536     }
537     assert(jumpAddrReg);
538     // In the pattern we've seen, if the instruction previous to this is
539     // an add with a result that ends up being used as the jump address,
540     // then we're adding a relative value we got from the table to a base
541     // address to get the jump address; in other words, the contents of
542     // the jump table are relative.
543     tableIsRelative = false;
544     if(patternIter != currentBlock->allInsns.begin())
545     {
546         patternIter--;
547         if(patternIter->second->getOperation().getID() == power_op_add &&
548            patternIter->second->isWritten(*(regs.begin())))
549         {
550             tableIsRelative = true;
551         }
552     }
553     parsing_printf(" TableIsRelative %d\n", tableIsRelative);
554
555     patternIter = currentBlock->curInsnIter;
556
557     jumpStartAddress = 0;
558     adjustEntry = 0;
559     tableStartAddress = 0;
560     adjustTableStartAddress = 0;
561     foundAdjustEntry = false;
562
563     parsing_printf("\t TOC_address 0x%lx\n", TOC_address);
564     if(!TOC_address)
565     {
566         // Find addi-addis instructions to determine the jump table start address.
567         // These instructions can be anywhere in the function before the
568         // indirect jump.Hence parse through the current block and previous block
569         // till we reach the function entry.
570         Block* worklistBlock = currBlk;
571         std::set <Block*> visited;
572         std::deque<Block*> worklist;
573         worklist.insert(worklist.begin(), worklistBlock);
574         visited.insert(worklistBlock);
575         Intraproc epred;
576         parsing_printf("Looking for table start address over blocks to function entry\n");
577         while(!worklist.empty())
578         {
579             worklistBlock= worklist.front();
580             worklist.pop_front();
581             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());
582             Address blockStart = worklistBlock->start();
583             const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
584             parsing_printf(" Block start 0x%lx \n", blockStart);
585             InstructionDecoder dec(b, worklistBlock->size(), currentBlock->_isrc->getArch());
586             IA_IAPI IABlock(dec, blockStart, currentBlock->_obj, currentBlock->_cr, currentBlock->_isrc, worklistBlock);
587
588             while(IABlock.getInstruction() && !IABlock.hasCFT()) {
589                 IABlock.advance();
590             }
591
592             patternIter = IABlock.curInsnIter;
593             findTableAddrNoTOC(&IABlock);
594             if(!jumpStartAddress)
595             {
596                 jumpStartAddress = tableStartAddress;
597             }
598             if (tableStartAddress != 0) {
599                 jumpStartAddress = tableStartAddress;
600                 parsing_printf("\t\tjumpStartAddress 0x%lx \n", jumpStartAddress);
601                 break;
602             }
603             std::for_each(boost::make_filter_iterator(epred, worklistBlock->sources().begin(), worklistBlock->sources().end()),
604                           boost::make_filter_iterator(epred, worklistBlock->sources().end(), worklistBlock->sources().end()),
605                           boost::bind(detail_ppc::processPredecessor, _1, boost::ref(visited), boost::ref(worklist)));
606
607         }
608
609     }
610     else if (tableIsRelative) {
611         if(!parseRelativeTableIdiom())
612         {
613             return false;
614         }
615     } else {
616         parsing_printf("\t Table is not relative and we know the TOC is 0x%lx, searching for table base\n",
617                        TOC_address);
618         foundAdjustEntry = false;
619
620         scanForAdjustOrBase(patternIter, currentBlock->allInsns.begin(), jumpAddrReg);
621
622         if (!tableStartAddress) {
623             // Keep looking in the immediate predecessor - XLC
624             for (Block::edgelist::const_iterator e_iter = currBlk->sources().begin();
625                  e_iter != currBlk->sources().end(); ++e_iter) {
626                 Address blockStart = (*e_iter)->src()->start();
627                 const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
628                 InstructionDecoder dec(b, (*e_iter)->src()->size(), currentBlock->_isrc->getArch());
629                 IA_IAPI IABlock(dec, blockStart, currentBlock->_obj, currentBlock->_cr, currentBlock->_isrc, (*e_iter)->src());
630
631                 // Cache instructions
632                 while(IABlock.getInstruction() && !IABlock.hasCFT()) {
633                     IABlock.advance();
634                 }
635
636                 IA_IAPI::allInsns_t::const_iterator localIter = IABlock.curInsnIter;
637                 findTableBase(localIter, IABlock.allInsns.begin());
638             }
639         }
640     }
641
642     const Block::edgelist & sourceEdges = currBlk->sources();
643     if(sourceEdges.size() != 1 || (*sourceEdges.begin())->type() == CALL) {
644         parsing_printf("%s[%d]: jump table not properly guarded, ret false\n", FILE__, __LINE__);
645         return false;
646     }
647
648
649
650     // We could also set this = jumpStartAddress...
651     if (tableStartAddress == 0)  {
652         parsing_printf("%s[%d]: couldn't find table start addr, ret false\n", FILE__, __LINE__);
653         return false;
654
655     }
656
657     parsing_printf("%s[%d]: table start addr is 0x%x\n", FILE__, __LINE__, tableStartAddress);
658     int maxSwitch = 0;
659
660     Block* sourceBlock = (*sourceEdges.begin())->src();
661     Address blockStart = sourceBlock->start();
662     const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
663     InstructionDecoder dec(b, sourceBlock->size(), currentBlock->_isrc->getArch());
664     IA_IAPI prevBlock(dec, blockStart,currentBlock->_obj,currentBlock->_cr,currentBlock->_isrc, sourceBlock);
665     while(!prevBlock.hasCFT() && prevBlock.getInstruction()) {
666         prevBlock.advance();
667     }
668
669     parsing_printf("%s[%d]: checking for max switch...\n", FILE__, __LINE__);
670     bool foundBranch = false;
671     IA_IAPI::allInsns_t::reverse_iterator iter;
672     for(iter = prevBlock.allInsns.rbegin(); iter != prevBlock.allInsns.rend(); iter++)
673
674     {
675         parsing_printf("\t\tchecking insn 0x%x: %s for cond branch + compare\n", iter->first,
676                        iter->second->format().c_str());
677         if(iter->second->getOperation().getID() == power_op_bc) // make this a true cond. branch check
678         {
679             foundBranch = true;
680         } else if(foundBranch &&
681                   (iter->second->getOperation().getID() == power_op_cmpi ||
682                    iter->second->getOperation().getID() == power_op_cmpli))
683         {
684             maxSwitch = iter->second->getOperand(2).getValue()->eval().convert<int>() + 1;
685             break;
686
687         }
688     }
689
690     parsing_printf("%s[%d]: After checking: max switch %d\n", FILE__, __LINE__, maxSwitch);
691     if(!maxSwitch){
692         return false;
693     }
694
695     Address jumpStart = 0;
696     Address tableStart = 0;
697     bool is64 = (currentBlock->_isrc->getAddressWidth() == 8);
698     std::vector<std::pair< Address, EdgeTypeEnum> > edges;
699
700     if(TOC_address)
701     {
702         if (tableIsRelative) {
703             void *jumpStartPtr = currentBlock->_isrc->getPtrToData(jumpStartAddress);
704             parsing_printf("%s[%d]: jumpStartPtr (0x%lx) = %p\n", FILE__, __LINE__, jumpStartAddress, jumpStartPtr);
705             if (jumpStartPtr)
706                 jumpStart = (is64
707                              ? *((Address  *)jumpStartPtr)
708                              : *((uint32_t *)jumpStartPtr));
709             parsing_printf("%s[%d]: jumpStart 0x%lx, initialAddr 0x%lx\n",
710                            FILE__, __LINE__, jumpStart, initialAddress);
711             if (jumpStartPtr == NULL) {
712                 return false;
713             }
714         }
715         void *tableStartPtr = currentBlock->_isrc->getPtrToData(tableStartAddress);
716         parsing_printf("%s[%d]: tableStartPtr (0x%lx) = %p\n", FILE__, __LINE__, tableStartAddress, tableStartPtr);
717         tableStart = *((Address *)tableStartPtr);
718         if (tableStartPtr)
719             tableStart = (is64
720                           ? *((Address  *)tableStartPtr)
721                           : *((uint32_t *)tableStartPtr));
722         else {
723             return false;
724         }
725         parsing_printf("\t... tableStart 0x%lx\n", tableStart);
726
727         bool tableData = false;
728         for(int i=0;i<maxSwitch;i++){
729             Address tableEntry = adjustEntry + tableStart + (i * 4 /*instruction::size()*/);
730             parsing_printf("\t\tTable entry at 0x%lx\n", tableEntry);
731             if (currentBlock->_isrc->isValidAddress(tableEntry)) {
732                 int jumpOffset;
733                 if (tableData) {
734                     jumpOffset = *((int *)currentBlock->_isrc->getPtrToData(tableEntry));
735                 }
736                 else {
737                     jumpOffset = *((int *)currentBlock->_isrc->getPtrToInstruction(tableEntry));
738                 }
739
740                 parsing_printf("\t\t\tjumpOffset 0x%lx\n", jumpOffset);
741                 Address res = (Address)(jumpStart + jumpOffset);
742
743                 if (currentBlock->_isrc->isCode(res)) {
744                     edges.push_back(std::make_pair((Address)(jumpStart+jumpOffset), INDIRECT));
745                     parsing_printf("\t\t\tEntry of 0x%lx\n", (Address)(jumpStart + jumpOffset));
746                 }
747             }
748             else {
749                 parsing_printf("\t\tAddress not valid!\n");
750             }
751         }
752     }
753         // No TOC, so we're on Power32 Linux.  Do the ELF thing.
754     else
755     {
756         jumpStart = jumpStartAddress;
757         tableStart = tableStartAddress;
758         parsing_printf(" jumpStartaddress 0x%lx tableStartAddress 0x%lx \n", jumpStartAddress, tableStartAddress);
759         if(toc_visitor->toc_contents)
760         {
761             void* tmp = NULL;
762             if(currentBlock->_isrc->isValidAddress(jumpStartAddress))
763             {
764                 tmp = currentBlock->_isrc->getPtrToData(jumpStartAddress);
765                 if(!tmp)
766                 {
767                     tmp = currentBlock->_isrc->getPtrToInstruction(jumpStartAddress);
768                 }
769                 if(tmp)
770                 {
771                     jumpStart = *((Address*)tmp);
772                     parsing_printf("\t\tjumpStart adjusted to 0x%lx\n", jumpStart);
773                 }
774             }
775             if(currentBlock->_isrc->isValidAddress(tableStartAddress))
776             {
777                 tmp = currentBlock->_isrc->getPtrToData(tableStartAddress);
778                 if(!tmp)
779                 {
780                     tmp = currentBlock->_isrc->getPtrToInstruction(tableStartAddress);
781                 }
782                 if(tmp)
783                 {
784                     tableStart = *((Address*)tmp);
785                     parsing_printf("\t\ttableStart adjusted to 0x%lx\n", jumpStart);
786                 }
787             }
788         }
789
790
791         if (jumpStart == 0) {
792 #if defined(WITH_SYMTAB_API)
793             // If jump table address is a relocation entry, this will be filled by the loader
794             // This case is common in shared library where the table address is in the GOT section which is filled by the loader
795             // Find the relocation entry for this address and look up its value
796
797             Block* sourceBlock = (*sourceEdges.begin())->src();
798             Address blockStart = sourceBlock->start();
799             const unsigned char* b = (const unsigned char*)(currentBlock->_isrc->getPtrToInstruction(blockStart));
800             InstructionDecoder dec(b, sourceBlock->size(), currentBlock->_isrc->getArch());
801             IA_IAPI IABlock(dec, blockStart,currentBlock->_obj,currentBlock->_cr,currentBlock->_isrc, sourceBlock);
802
803             SymtabCodeSource *scs = dynamic_cast<SymtabCodeSource *>(IABlock._obj->cs());
804             SymtabAPI::Symtab * symtab = scs->getSymtabObject();
805             std::vector<SymtabAPI::Region *> regions;
806             symtab->getAllRegions(regions);
807             for (unsigned index = 0 ; index < regions.size(); index++) {
808                 if (regions[index]->getRegionType() == SymtabAPI::Region::RT_RELA ||
809                     regions[index]->getRegionType() == SymtabAPI::Region::RT_REL) {
810                     std::vector<SymtabAPI::relocationEntry> relocs =
811                             regions[index]->getRelocations();
812                     parsing_printf(" \t\trelocation size %d looking for 0x%lx\n", relocs.size(), jumpStartAddress);
813                     for (unsigned i = 0; i < relocs.size(); ++i) {
814                         parsing_printf(" \t 0x%lx => 0x%lx addend 0x%lx \n", relocs[i].rel_addr(),relocs[i].target_addr(), relocs[i].addend());
815                         if (relocs[i].rel_addr() == jumpStartAddress) {
816                             jumpStart = relocs[i].addend();
817                             break;
818                         }
819                     }
820                     break;
821                 }
822             }
823 #else
824             // Can't parse relocation entries without Symtab
825         return false;
826 #endif
827         }
828         if (tableStart == 0) tableStart = jumpStart;
829
830         if (!tableIsRelative) {
831             jumpStart = 0;
832         }
833         parsing_printf(" jumpStartaddress 0x%lx tableStartAddress 0x%lx \n", jumpStart, tableStart);
834
835         int entriesAdded = 0;
836         for(int i = 0; i < maxSwitch; i++)
837         {
838             void* ptr = NULL;
839             Address tableEntry = tableStart + i*4; // instruction::size();
840             if(currentBlock->_isrc->isValidAddress(tableEntry))
841             {
842                 ptr = currentBlock->_isrc->getPtrToInstruction(tableEntry);
843             }
844             if(ptr)
845             {
846                 int jumpOffset = *((int *)ptr);
847                 edges.push_back(std::make_pair((Address)(jumpStart+jumpOffset), INDIRECT));
848                 parsing_printf("\t\t\t[0x%lx] -> 0x%lx (0x%lx in table)\n", tableEntry,
849                                jumpStart+jumpOffset,
850                                jumpOffset);
851                 ++entriesAdded;
852             }
853             else
854             {
855                 parsing_printf("\t\t\t[0x%lx] -> [INVALID]\n", tableEntry);
856             }
857         }
858         if(!entriesAdded)
859         {
860             parsing_printf("%s[%d]: no entries added from jump table, returning false\n", FILE__, __LINE__);
861             return false;
862         }
863         parsing_printf("%s[%d]: Found %d entries in jump table, returning success\n", FILE__, __LINE__, entriesAdded);
864     }
865
866     // Sanity check entries in res
867     for (std::vector<std::pair<Address, EdgeTypeEnum> >::iterator iter = edges.begin();
868          iter != edges.end(); iter++) {
869         if ((iter->first) % 4) {
870             parsing_printf("Warning: found unaligned jump table destination 0x%lx for jump at 0x%lx, disregarding table\n",
871                            iter->first, initialAddress);
872             return false;
873         }
874     }
875     // If we have found a jump table, add the targets to outEdges
876     for (std::vector<std::pair<Address, EdgeTypeEnum> >::iterator iter = edges.begin();
877          iter != edges.end(); iter++) {
878         parsing_printf("Adding out edge %d/0x%lx\n", iter->second, iter->first);
879         outEdges.push_back(*iter);
880     }
881     return true;
882 }