Start to split jump table analysis to two different slices.
[dyninst.git] / parseAPI / src / SymbolicExpression.C
1 #include "SymbolicExpression.h"
2 #include "SymEval.h"
3 #include "Absloc.h"
4 #include "debug_parse.h"
5 #include "IndirectASTVisitor.h"
6 #include "CFG.h"
7 #include "CodeSource.h"
8 #include "CodeObject.h"
9 using namespace std;
10 using namespace Dyninst;
11 using namespace Dyninst::ParseAPI;
12 using namespace Dyninst::DataflowAPI;
13 AST::Ptr SymbolicExpression::SimplifyRoot(AST::Ptr ast, Address addr) {
14     if (ast->getID() == AST::V_RoseAST) {
15         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast); 
16         
17         switch (roseAST->val().op) {
18             case ROSEOperation::invertOp:
19                 if (roseAST->child(0)->getID() == AST::V_RoseAST) {
20                     RoseAST::Ptr child = boost::static_pointer_cast<RoseAST>(roseAST->child(0));
21                     if (child->val().op == ROSEOperation::invertOp) return child->child(0);
22                 } else if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
23                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
24                     size_t size = child->val().size;
25                     uint64_t val = child->val().val;
26                     if (size < 64) {
27                         uint64_t mask = (1ULL << size) - 1;
28                         val = (~val) & mask;
29                     } else
30                         val = ~val;
31                     return ConstantAST::create(Constant(val, size));
32                 }
33                 break;
34             case ROSEOperation::extendMSBOp:
35             case ROSEOperation::extractOp:
36             case ROSEOperation::signExtendOp:
37             case ROSEOperation::concatOp:
38                 return roseAST->child(0);
39
40             case ROSEOperation::addOp:
41                 // We simplify the addition as much as we can
42                 // Case 1: two constants
43                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
44                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
45                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
46                     uint64_t val = child0->val().val + child1->val().val;
47                     size_t size;
48                     if (child0->val().size > child1->val().size)
49                         size = child0->val().size;
50                     else
51                         size = child1->val().size;
52                     return ConstantAST::create(Constant(val,size));
53                 }
54                 // Case 2: anything adding zero stays the same
55                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
56                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
57                     if (child->val().val == 0) return roseAST->child(1);
58                 }
59                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
60                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
61                     if (child->val().val == 0) return roseAST->child(0);
62                 }
63                 // Case 3: if v + v * c = v * (c+1), where v is a variable and c is a constant
64                 if (roseAST->child(0)->getID() == AST::V_VariableAST && roseAST->child(1)->getID() == AST::V_RoseAST) {
65                     RoseAST::Ptr rOp = boost::static_pointer_cast<RoseAST>(roseAST->child(1));
66                     if (rOp->val().op == ROSEOperation::uMultOp || rOp->val().op == ROSEOperation::sMultOp) {
67                         if (rOp->child(0)->getID() == AST::V_VariableAST && rOp->child(1)->getID() == AST::V_ConstantAST) {
68                             VariableAST::Ptr varAST1 = boost::static_pointer_cast<VariableAST>(roseAST->child(0));
69                             VariableAST::Ptr varAST2 = boost::static_pointer_cast<VariableAST>(rOp->child(0));
70                             if (varAST1->val().reg == varAST2->val().reg) {
71                                 ConstantAST::Ptr oldC = boost::static_pointer_cast<ConstantAST>(rOp->child(1));
72                                 ConstantAST::Ptr newC = ConstantAST::create(Constant(oldC->val().val + 1, oldC->val().size));
73                                 RoseAST::Ptr newRoot = RoseAST::create(ROSEOperation(rOp->val()), varAST1, newC);
74                                 return newRoot;
75                             }
76                         }
77                     }
78                 } 
79                 break;
80             case ROSEOperation::sMultOp:
81             case ROSEOperation::uMultOp:
82                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
83                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
84                     if (child0->val().val == 1) return roseAST->child(1);
85                 }
86
87                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
88                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
89                     if (child1->val().val == 1) return roseAST->child(0);
90                 }
91                 break;
92
93             case ROSEOperation::xorOp:
94                 if (roseAST->child(0)->getID() == AST::V_VariableAST && roseAST->child(1)->getID() == AST::V_VariableAST) {
95                     VariableAST::Ptr child0 = boost::static_pointer_cast<VariableAST>(roseAST->child(0)); 
96                     VariableAST::Ptr child1 = boost::static_pointer_cast<VariableAST>(roseAST->child(1)); 
97                     if (child0->val() == child1->val()) {
98                         return ConstantAST::create(Constant(0 , 32));
99                     }
100                 }
101                 break;
102             case ROSEOperation::derefOp:
103                 // Any 8-bit value is bounded in [0,255].
104                 // Need to keep the length of the dereference if it is 8-bit.
105                 // However, dereference longer than 8-bit should be regarded the same.
106                 if (roseAST->val().size == 8)
107                     return ast;
108                 else
109                     return RoseAST::create(ROSEOperation(ROSEOperation::derefOp), ast->child(0));
110                 break;
111             case ROSEOperation::shiftLOp:
112                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
113                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
114                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
115                     return ConstantAST::create(Constant(child0->val().val << child1->val().val, 64));
116                 }
117                 break;
118             case ROSEOperation::andOp:
119                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
120                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
121                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
122                     return ConstantAST::create(Constant(child0->val().val & child1->val().val, 64));
123                 }
124                 break;
125             case ROSEOperation::orOp:
126                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
127                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
128                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
129                     return ConstantAST::create(Constant(child0->val().val | child1->val().val, 64));
130                 }
131                 break;
132
133             default:
134                 break;
135
136         }
137     } else if (ast->getID() == AST::V_VariableAST) {
138         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
139         if (varAST->val().reg.absloc().isPC()) {
140             MachRegister pc = varAST->val().reg.absloc().reg();     
141             return ConstantAST::create(Constant(addr, getArchAddressWidth(pc.getArchitecture()) * 8));
142         }
143         // We do not care about the address of the a-loc
144         // because we will keep tracking the changes of 
145         // each a-loc. Also, this brings a benefit that
146         // we can directly use ast->isStrictEqual() to 
147         // compare two ast.
148         return VariableAST::create(Variable(varAST->val().reg));
149     } else if (ast->getID() == AST::V_ConstantAST) {
150         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast);
151         size_t size = constAST->val().size;
152         uint64_t val = constAST->val().val;     
153         if (size == 32)
154             if (!(val & (1ULL << (size - 1))))
155                 return ConstantAST::create(Constant(val, 64));
156     }
157
158     return ast;
159 }
160
161
162 AST::Ptr SymbolicExpression::SimplifyAnAST(AST::Ptr ast, Address addr) {
163     SimplifyVisitor sv(addr);
164     ast->accept(&sv);
165     return SimplifyRoot(ast, addr);
166 }
167
168 bool SymbolicExpression::ContainAnAST(AST::Ptr root, AST::Ptr check) {
169     if (*root == *check) return true;
170     bool ret = false;
171     unsigned totalChildren = root->numChildren();
172     for (unsigned i = 0 ; i < totalChildren && !ret; ++i) {
173         ret |= ContainAnAST(root->child(i), check);
174     }
175     return ret;
176 }
177
178
179 AST::Ptr SymbolicExpression::DeepCopyAnAST(AST::Ptr ast) {
180     if (ast->getID() == AST::V_RoseAST) {
181         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast);
182         AST::Children kids;
183         unsigned totalChildren = ast->numChildren();
184         for (unsigned i = 0 ; i < totalChildren; ++i) {
185             kids.push_back(DeepCopyAnAST(ast->child(i)));
186         }
187         return RoseAST::create(ROSEOperation(roseAST->val()), kids);
188     } else if (ast->getID() == AST::V_VariableAST) {
189         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
190         return VariableAST::create(Variable(varAST->val()));
191     } else if (ast->getID() == AST::V_ConstantAST) {
192         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast);
193         return ConstantAST::create(Constant(constAST->val()));
194     } else if (ast->getID() == AST::V_BottomAST) {
195         BottomAST::Ptr bottomAST = boost::static_pointer_cast<BottomAST>(ast);
196         return BottomAST::create(bottomAST->val());
197     }
198     fprintf(stderr, "ast type %d, %s\n", ast->getID(), ast->format().c_str());
199     assert(0);
200         return AST::Ptr();
201 }
202
203 pair<AST::Ptr, bool> SymbolicExpression::ExpandAssignment(Assignment::Ptr assign) {
204     if (expandCache.find(assign) != expandCache.end()) {
205         AST::Ptr ast = expandCache[assign];
206         if (ast) return make_pair(ast, true); else return make_pair(ast, false);
207     } else {
208         parsing_printf("\t\tExpanding instruction @ %x: %s\n", assign->addr(), assign->insn()->format().c_str());
209         pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
210         if (expandRet.second && expandRet.first) {
211             parsing_printf("Original expand: %s\n", expandRet.first->format().c_str());
212             AST::Ptr calculation = SimplifyAnAST(expandRet.first, 
213                                                  PCValue(assign->addr(),
214                                                          assign->insn()->size(),
215                                                          assign->block()->obj()->cs()->getArch()));
216             expandCache[assign] = calculation;
217         } else {
218             expandCache[assign] = AST::Ptr();
219         }
220         return make_pair( expandCache[assign], expandRet.second );
221     }
222 }
223
224 AST::Ptr SymbolicExpression::SubstituteAnAST(AST::Ptr ast, const map<AST::Ptr, AST::Ptr> &aliasMap) {
225     for (auto ait = aliasMap.begin(); ait != aliasMap.end(); ++ait)
226         if (*ast == *(ait->first)) {
227             return ait->second;
228         }
229     unsigned totalChildren = ast->numChildren();
230     for (unsigned i = 0 ; i < totalChildren; ++i) {
231         ast->setChild(i, SubstituteAnAST(ast->child(i), aliasMap));
232     }
233     if (ast->getID() == AST::V_VariableAST) {
234         // If this variable is not in the aliasMap yet,
235         // this variable is from the input.
236         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
237         return VariableAST::create(Variable(varAST->val().reg, 1));
238     }
239     return ast;
240 }
241
242 Address SymbolicExpression::PCValue(Address cur, size_t insnSize, Architecture a) {
243     switch (a) {
244         case Arch_x86:
245         case Arch_x86_64:
246             return cur + insnSize;
247         case Arch_aarch64:
248             return cur;
249         case Arch_aarch32:
250         case Arch_ppc32:
251         case Arch_ppc64:
252         case Arch_none:
253             assert(0);
254     }    
255     return cur + insnSize;
256 }