Add compiler-specific search directories in getResolvedLibraryPath (#732)
[dyninst.git] / parseAPI / src / IndirectASTVisitor.C
1 #include "dyntypes.h"
2 #include "IndirectASTVisitor.h"
3 #include "debug_parse.h"
4 #include "CodeObject.h"
5 #include <algorithm>
6 using namespace Dyninst::ParseAPI;
7
8 AST::Ptr SimplifyVisitor::visit(DataflowAPI::RoseAST *ast) {
9         unsigned totalChildren = ast->numChildren();
10         for (unsigned i = 0 ; i < totalChildren; ++i) {
11             ast->child(i)->accept(this);
12             ast->setChild(i, se.SimplifyRoot(ast->child(i), addr, keepMultiOne));
13         }
14         return AST::Ptr();
15 }
16
17 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::RoseAST *ast) {
18     StridedInterval *astBound = boundFact.GetBound(ast);
19     if (astBound != NULL) {
20         bound.insert(make_pair(ast, new StridedInterval(*astBound)));
21         return AST::Ptr();
22     }
23     unsigned totalChildren = ast->numChildren();
24     for (unsigned i = 0 ; i < totalChildren; ++i) {
25         ast->child(i)->accept(this);
26     }
27     switch (ast->val().op) {
28         case ROSEOperation::addOp:
29             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {         
30                 StridedInterval* val = new StridedInterval(*GetResultBound(ast->child(0)));             
31                 val->Add(*GetResultBound(ast->child(1)));
32                 if (*val != StridedInterval::top)
33                     bound.insert(make_pair(ast, val));
34             }       
35             break;
36         case ROSEOperation::invertOp:
37             if (IsResultBounded(ast->child(0))) {
38                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
39                 val->Not();
40                 if (*val != StridedInterval::top)
41                     bound.insert(make_pair(ast,val));
42             }
43             break;
44         case ROSEOperation::andOp: {
45             // For and operation, even one of them is a top,
46             // we may still produce bound result.
47             // For example, top And 0[3,3] => 1[0,3]
48             //
49             // the bound produced by and may be more relaxed than
50             // a cmp bound not found yet. So we only apply and
51             // bound when this is the last attempt
52             if (handleOneByteRead) {
53                 parsing_printf("\tTry to generate bound for AND\n");
54                 StridedInterval *val = NULL;
55                 if (IsResultBounded(ast->child(0)))
56                     val = new StridedInterval(*GetResultBound(ast->child(0)));
57                 else
58                     val = new StridedInterval(StridedInterval::top);
59                 if (IsResultBounded(ast->child(1)))
60                     val->And(*GetResultBound(ast->child(1)));
61                 else
62                     val->And(StridedInterval::top);
63                 // the result of an AND operation should not be
64                 // the table lookup. Set all other values to default
65                 if (*val != StridedInterval::top)
66                     bound.insert(make_pair(ast, val));
67             }
68             break;
69         }
70         case ROSEOperation::sMultOp:
71         case ROSEOperation::uMultOp:
72             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
73                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
74                 val->Mul(*GetResultBound(ast->child(1)));
75                 if (*val != StridedInterval::top)
76                     bound.insert(make_pair(ast, val));
77             }
78             break;
79         case ROSEOperation::shiftLOp:
80         case ROSEOperation::rotateLOp:
81             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
82                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
83                 val->ShiftLeft(*GetResultBound(ast->child(1)));
84                 if (*val != StridedInterval::top)
85                     bound.insert(make_pair(ast, val));
86             }
87             break;
88         case ROSEOperation::shiftROp:
89         case ROSEOperation::rotateROp:
90             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
91                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
92                 val->ShiftRight(*GetResultBound(ast->child(1)));
93                 if (*val != StridedInterval::top)
94                     bound.insert(make_pair(ast, val));
95             }
96             break;
97         case ROSEOperation::derefOp: 
98             if (handleOneByteRead && ast->val().size == 8) {
99                 // Any 8-bit value is bounded in [0,255]
100                 // But I should only do this when I know the read 
101                 // itself is not a jump table
102                 bound.insert(make_pair(ast, new StridedInterval(1,0,255)));
103             }
104             break;
105         case ROSEOperation::orOp: 
106             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
107                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
108                 val->Or(*GetResultBound(ast->child(1)));
109                 if (*val != StridedInterval::top)
110                     bound.insert(make_pair(ast, val));
111             }
112             break;
113         case ROSEOperation::ifOp:
114             if (IsResultBounded(ast->child(1)) && IsResultBounded(ast->child(2))) {
115                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(1)));
116                 val->Join(*GetResultBound(ast->child(2)));
117                 if (*val != StridedInterval::top)
118                     bound.insert(make_pair(ast, val));
119             }
120         default:
121             break;
122     }
123     return AST::Ptr();
124    
125 }
126
127 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::ConstantAST *ast) {
128     const Constant &v = ast->val();
129     int64_t value = v.val;
130     if (v.size != 1 && v.size != 64 && (value & (1ULL << (v.size - 1)))) {
131         // Compute the two complements in bits of v.size
132         // and change it to a negative number
133         value = -(((~value) & ((1ULL << v.size) - 1)) + 1);
134     }
135     parsing_printf("\t\tGet a constant %ld\n", value);
136     bound.insert(make_pair(ast, new StridedInterval(value)));
137     return AST::Ptr();
138 }
139
140 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::VariableAST *ast) {
141     StridedInterval *astBound = boundFact.GetBound(ast);
142     if (astBound != NULL) 
143         bound.insert(make_pair(ast, new StridedInterval(*astBound)));
144     return AST::Ptr();
145 }
146
147 StridedInterval* BoundCalcVisitor::GetResultBound(AST::Ptr ast) {
148     if (IsResultBounded(ast)) {
149         return bound.find(ast.get())->second;
150     } else {
151         return NULL;
152     }       
153 }
154
155 BoundCalcVisitor::~BoundCalcVisitor() {
156     for (auto bit = bound.begin(); bit != bound.end(); ++bit)
157         if (bit->second != NULL)
158             delete bit->second;
159     bound.clear();
160 }
161
162
163 AST::Ptr JumpCondVisitor::visit(DataflowAPI::RoseAST *ast) {
164     if (ast->val().op == ROSEOperation::invertOp) {
165         invertFlag = true;
166         return AST::Ptr();
167     }
168     unsigned totalChildren = ast->numChildren();
169     for (unsigned i = 0 ; i < totalChildren; ++i) {
170         ast->child(i)->accept(this);
171     }
172     return AST::Ptr();
173 }
174
175 AST::Ptr ComparisonVisitor::visit(DataflowAPI::RoseAST *ast) {
176     // For cmp type instruction setting zf
177     // Looking like <eqZero?>(<add>(<V([x86_64::rbx])>,<Imm:8>,),)
178     // Assuming ast has been simplified
179     unsigned totalChildren = ast->numChildren();
180     for (unsigned i = 0 ; i < totalChildren; ++i) {
181         ast->child(i)->accept(this);
182     }
183     if (ast->val().op == ROSEOperation::equalToZeroOp && !subtrahend) {
184         bool minuendIsZero = true;
185         AST::Ptr child = ast->child(0); 
186         if (child->getID() == AST::V_RoseAST) {
187             RoseAST::Ptr childRose = boost::static_pointer_cast<RoseAST>(child);
188             if (childRose->val().op == ROSEOperation::addOp) {
189                 minuendIsZero = false;
190                 subtrahend = childRose->child(0);
191                 minuend = childRose->child(1);
192                 // If the minuend is a constant, then
193                 // the minuend is currently in its two-complement form
194                 if (minuend->getID() == AST::V_ConstantAST) {
195                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(minuend);
196                     uint64_t val = constAST->val().val;
197                     int size = constAST->val().size;
198                     if (size < 64) 
199                         val = ((~val)+ 1) & ((1ULL << size) - 1);
200                     else if (size == 64)
201                         val = (~val) + 1;
202                     else
203                         parsing_printf("WARNING: constant bit size %d exceeds 64!\n", size);
204                     minuend = ConstantAST::create(Constant(val, size));
205                 } else if (minuend->getID() == AST::V_RoseAST) {
206                     RoseAST::Ptr sub = boost::static_pointer_cast<RoseAST>(minuend);
207                     minuend = AST::Ptr();
208                     if (sub->val().op == ROSEOperation::addOp && sub->child(0)->getID() == AST::V_RoseAST) {
209                         sub = boost::static_pointer_cast<RoseAST>(sub->child(0));
210                         if (sub->val().op == ROSEOperation::invertOp) {
211                             // Otherwise, the minuend ast is in the form of add(invert(minuend), 1)
212                             // Need to extract the real minuend
213                              minuend = sub->child(0);
214                         }
215                     }
216                 }
217             }   
218             if (childRose->val().op == ROSEOperation::xorOp) {
219                 minuendIsZero = false;
220                 subtrahend = childRose->child(0);
221                 minuend = childRose->child(1);
222             }
223
224         } 
225         if (minuendIsZero) {
226             // The minuend is 0, thus the add operation is subsume.
227              subtrahend = ast->child(0);
228              minuend = ConstantAST::create(Constant(0));
229         }
230     }
231     return AST::Ptr();
232 }
233
234 JumpTableFormatVisitor::JumpTableFormatVisitor(ParseAPI::Block *bl) {
235     b = bl;
236     numOfVar = 0;
237     memoryReadLayer = 0; 
238     findIncorrectFormat = false;
239     findTableBase = false;
240     findIndex = false;
241     firstAdd = true;
242 }
243
244 AST::Ptr JumpTableFormatVisitor::visit(DataflowAPI::RoseAST *ast) {
245     if (ast->val().op == ROSEOperation::derefOp) {
246         memoryReadLayer++;
247         if (memoryReadLayer > 1) {
248             parsing_printf("More than one layer of memory accesses, not jump table format\n");
249             findIncorrectFormat = true;
250             return AST::Ptr();
251         }
252         ast->child(0)->accept(this);
253         memoryReadLayer--;
254         return AST::Ptr();
255     }
256
257     if (ast->val().op == ROSEOperation::addOp && memoryReadLayer > 0 && firstAdd) {
258         firstAdd = false;
259         Address tableBase = 0;
260         if (ast->child(0)->getID() == AST::V_ConstantAST && PotentialIndexing(ast->child(1))) {
261             ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast->child(0));
262             tableBase = (Address)constAST->val().val;
263         }
264         if (ast->child(1)->getID() == AST::V_ConstantAST && PotentialIndexing(ast->child(0))) {
265             ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast->child(1));
266             tableBase = (Address)constAST->val().val;
267         }
268         if (tableBase) {
269             Architecture arch = b->obj()->cs()->getArch();
270             if (arch == Arch_x86) {
271                 tableBase &= 0xffffffff;
272             }
273 #if defined(os_windows)
274             tableBase -= b->obj()->cs()->loadAddress();
275 #endif
276             if (!b->obj()->cs()->isValidAddress(tableBase)) {
277                 parsing_printf("\ttableBase 0x%lx invalid, not jump table format\n", tableBase);
278                 findIncorrectFormat = true;
279                 return AST::Ptr();
280             }
281 /*
282             if (!b->obj()->cs()->isReadOnly(tableBase)) {
283                 parsing_printf("\ttableBase 0x%lx not read only, not jump table format\n", tableBase);
284                 findIncorrectFormat = true;
285                 return AST::Ptr();
286             }
287 */          
288             findTableBase = true;
289        }
290     } 
291     
292     if ((ast->val().op == ROSEOperation::uMultOp || 
293          ast->val().op == ROSEOperation::sMultOp || 
294          ast->val().op == ROSEOperation::shiftLOp ||
295          ast->val().op == ROSEOperation::rotateLOp) && memoryReadLayer > 0) {
296         if (ast->child(0)->getID() == AST::V_ConstantAST && ast->child(1)->getID() == AST::V_VariableAST) {
297             ConstantAST::Ptr constAst = boost::static_pointer_cast<ConstantAST>(ast->child(0));    
298             if (!((ast->val().op == ROSEOperation::uMultOp || ast->val().op == ROSEOperation::sMultOp) &&
299                 !findTableBase &&
300                 constAst->val().val == 1)) {
301                 findIndex = true;
302                 numOfVar++;
303                 VariableAST::Ptr varAst = boost::static_pointer_cast<VariableAST>(ast->child(1));
304                 index = varAst->val().reg;
305                 return AST::Ptr();
306             }
307         }
308         if (ast->child(1)->getID() == AST::V_ConstantAST && ast->child(0)->getID() == AST::V_VariableAST) {
309             ConstantAST::Ptr constAst = boost::static_pointer_cast<ConstantAST>(ast->child(1));    
310             if (!((ast->val().op == ROSEOperation::uMultOp || ast->val().op == ROSEOperation::sMultOp) &&
311                 !findTableBase &&
312                 constAst->val().val == 1)) {
313                 findIndex = true;
314                 numOfVar++;
315                 VariableAST::Ptr varAst = boost::static_pointer_cast<VariableAST>(ast->child(0));
316                 index = varAst->val().reg;
317                 return AST::Ptr();
318             }
319         }
320     }
321
322     unsigned totalChildren = ast->numChildren();
323     for (unsigned i = 0 ; i < totalChildren; ++i) {
324         ast->child(i)->accept(this);
325     }
326
327     return AST::Ptr();
328 }
329
330 AST::Ptr JumpTableFormatVisitor::visit(DataflowAPI::VariableAST *) {
331     numOfVar++;
332     return AST::Ptr();
333 }
334
335 bool JumpTableFormatVisitor::PotentialIndexing(AST::Ptr ast) {
336     if (ast->getID() == AST::V_VariableAST) return true;
337     if (ast->getID() == AST::V_RoseAST) {
338         RoseAST::Ptr r = boost::static_pointer_cast<RoseAST>(ast);
339         if (r->val().op == ROSEOperation::uMultOp || 
340             r->val().op == ROSEOperation::sMultOp || 
341             r->val().op == ROSEOperation::shiftLOp || 
342             r->val().op == ROSEOperation::rotateLOp) {
343             if (r->child(0)->getID() == AST::V_RoseAST) {
344                 return false;
345             }
346             return true;
347         }
348         if (r->val().op == ROSEOperation::addOp) {
349             // The index can be subtracted 
350             if (r->child(0)->getID() == AST::V_RoseAST && r->child(1)->getID() == AST::V_ConstantAST) {
351                 RoseAST::Ptr lc = boost::static_pointer_cast<RoseAST>(r->child(0));
352                 ConstantAST::Ptr rc = boost::static_pointer_cast<ConstantAST>(r->child(1));
353                 if (lc->val().op == ROSEOperation::invertOp && rc->val().val == 1) {
354                     return PotentialIndexing(lc->child(0));
355                 }
356             }
357         }
358     }
359     return false;
360 }
361
362 JumpTableReadVisitor::JumpTableReadVisitor(AbsRegion i, int v, CodeSource *c, CodeRegion *r, bool ze, int m) {
363     index = i;
364     indexValue = v;
365     cs = c;
366     cr = r;
367     isZeroExtend = ze;
368     valid = true;
369     memoryReadSize = m;
370 }
371
372 AST::Ptr JumpTableReadVisitor::visit(DataflowAPI::RoseAST *ast) {
373     unsigned totalChildren = ast->numChildren();
374     for (unsigned i = 0 ; i < totalChildren; ++i) {
375         ast->child(i)->accept(this);
376         if (!valid) return AST::Ptr();
377     }
378
379     // As soon as we do not know the value of one child, we will return.
380     // So, we will always have good values for each child at this point.
381     switch (ast->val().op) {
382         case ROSEOperation::addOp:
383             results.insert(make_pair(ast, results[ast->child(0).get()] + results[ast->child(1).get()]));
384             break;
385         case ROSEOperation::invertOp:
386             results.insert(make_pair(ast, ~results[ast->child(0).get()]));
387             break;
388         case ROSEOperation::andOp: 
389             results.insert(make_pair(ast, results[ast->child(0).get()] & results[ast->child(1).get()]));
390             break;
391         case ROSEOperation::sMultOp:
392         case ROSEOperation::uMultOp:
393             results.insert(make_pair(ast, results[ast->child(0).get()] * results[ast->child(1).get()]));
394             break;
395         case ROSEOperation::shiftLOp:
396         case ROSEOperation::rotateLOp:
397             results.insert(make_pair(ast, results[ast->child(0).get()] << results[ast->child(1).get()]));
398             break;
399         case ROSEOperation::shiftROp:
400         case ROSEOperation::rotateROp:
401             results.insert(make_pair(ast, results[ast->child(0).get()] >> results[ast->child(1).get()]));
402             break;
403         case ROSEOperation::derefOp: {
404                 int64_t v;
405                 bool validRead = PerformMemoryRead(results[ast->child(0).get()], v);
406                 if (!validRead) {
407                     valid = false;
408                     // We encounter an invalid table entry
409                     parsing_printf("WARNING: invalid table entry for index value %ld\n", indexValue);
410                     return AST::Ptr();
411                 }
412                 results.insert(make_pair(ast, v));
413             }
414             break;
415         case ROSEOperation::orOp: 
416             results.insert(make_pair(ast, results[ast->child(0).get()] | results[ast->child(1).get()]));
417             break;
418         default:
419             parsing_printf("WARNING: unhandled operation in the jump table format AST!\n");
420             valid = false;
421             break;
422     }
423     targetAddress = results[ast];
424     if (cs->getAddressWidth() == 4) {
425         targetAddress &= 0xffffffff;
426     }
427 #if defined(os_windows)
428     targetAddress -= cs->loadAddress();
429 #endif
430
431     return AST::Ptr();
432    
433 }
434
435 AST::Ptr JumpTableReadVisitor::visit(DataflowAPI::ConstantAST *ast) {
436     const Constant &v = ast->val();
437     int64_t value = v.val;
438     if (v.size != 1 && v.size != 64 && (value & (1ULL << (v.size - 1)))) {
439         // Compute the two complements in bits of v.size
440         // and change it to a negative number
441         value = -(((~value) & ((1ULL << v.size) - 1)) + 1);
442     }
443     results.insert(make_pair(ast, value));
444     return AST::Ptr();
445 }
446
447
448 AST::Ptr JumpTableReadVisitor::visit(DataflowAPI::VariableAST * var) {
449     if (var->val().reg != index) {
450         // The only variable in the jump table format AST should the index.
451         // If it is not the case, something is wrong
452         parsing_printf("WARNING: the jump table format AST contains a variable that is not the index\n");
453         valid = false;
454     }
455     results.insert(make_pair(var, indexValue));
456     return AST::Ptr();
457 }
458
459
460 bool JumpTableReadVisitor::PerformMemoryRead(Address addr, int64_t &v) {
461     readAddress = addr;
462     int addressWidth = cs->getAddressWidth();
463     if (addressWidth == 4) {
464         addr &= 0xffffffff;
465     }
466
467 #if defined(os_windows)
468     addr -= cs->loadAddress();
469 #endif
470     if (!cs->isCode(addr) && !cs->isData(addr)) return false;
471 //    if (!cs->isReadOnly(addr)) return false;
472     switch (memoryReadSize) {
473         case 8:
474             v = *(const uint64_t *) cs->getPtrToInstruction(addr);
475             break;
476         case 4:
477             v = *(const uint32_t *) cs->getPtrToInstruction(addr);
478             if (isZeroExtend) break;
479             if ((addressWidth == 8) && (v & 0x80000000)) {
480                 v |= SIGNEX_64_32;
481             }
482             break;
483         case 2:
484             v = *(const uint16_t *) cs->getPtrToInstruction(addr);
485             if (isZeroExtend) break;
486             if ((addressWidth == 8) && (v & 0x8000)) {
487                 v |= SIGNEX_64_16;
488             }
489             if ((addressWidth == 4) && (v & 0x8000)) {
490                 v |= SIGNEX_32_16;
491             }
492             break;
493         case 1:
494             v = *(const uint8_t *) cs->getPtrToInstruction(addr);
495             if (isZeroExtend) break;
496             if ((addressWidth == 8) && (v & 0x80)) {
497                 v |= SIGNEX_64_8;
498             }
499             if ((addressWidth == 4) && (v & 0x80)) {
500                 v |= SIGNEX_32_8;
501             }
502             break;          
503         default:
504             parsing_printf("Invalid memory read size %d\n", memoryReadSize);
505             return false;
506     }
507     return true;
508 }