Fix a mapping problem from Dyninst MachRegister to Rose register
[dyninst.git] / parseAPI / src / BoundFactCalculator.C
1 #include "CodeObject.h"
2 #include "CodeSource.h"
3
4 #include "IndirectControlFlow.h"
5 #include "IndirectASTVisitor.h"
6 #include "debug_parse.h"
7
8 bool BoundFactsCalculator::CalculateBoundedFacts() {    
9     /* We use a dataflow analysis to calculate what registers are bounded 
10      * at each node. The key points of the dataflow analysis are how
11      * to calculate the meet and how to calculate the transfer function.
12      * 1. The meet should be simply an intersection of all the bounded facts 
13      * along all paths. 
14      * 2. To calculate the transfer function, we first get the symbolic expression
15      * of the instrution for the node. Then depending on the instruction operation
16      * and the meet result, we know what are still bounded. For example, loading 
17      * memory is always unbounded; doing and operation on a register with a constant
18      * makes the register bounded. 
19      */
20     
21
22     queue<Node::Ptr> workingList;
23     map<Node::Ptr, int> inQueueLimit;
24
25     NodeIterator nbegin, nend;
26     slice->allNodes(nbegin, nend);
27
28     for (; nbegin != nend; ++nbegin) {
29         workingList.push(*nbegin);
30     }
31
32
33     while (!workingList.empty()) {
34         Node::Ptr curNode = workingList.front();
35         workingList.pop();
36
37         ++inQueueLimit[curNode];
38         if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
39
40         BoundFact* oldFact = GetBoundFact(curNode);
41         BoundFact* newFact = Meet(curNode);
42         CalcTransferFunction(curNode, newFact);
43
44         if (oldFact == NULL || *oldFact != *newFact) {
45             if (oldFact != NULL) delete oldFact;
46             boundFacts[curNode] = newFact;
47             curNode->outs(nbegin, nend);
48             for (; nbegin != nend; ++nbegin)
49                 workingList.push(*nbegin);
50         }
51     }
52
53     return true;
54 }
55
56
57 void BoundFactsCalculator::ConditionalJumpBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
58
59     /* This function checks whether any potential table guard is between the two nodes
60      * that we are calculating the meet. Essentially, if there is a conditional jump 
61      * between the two nodes, we know extra bound information.     
62      */   
63
64     ParseAPI::Block *srcBlock;
65     if (src == Node::Ptr()) 
66         srcBlock = func->entry();
67     else {
68         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
69         srcBlock = srcNode->block();
70
71     }
72     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
73     ParseAPI::Block *trgBlock = trgNode->block();
74
75     for (auto git = guards.begin(); git != guards.end(); ++git) {
76         parsing_printf("Checking guard at %lx\n", git->jmpInsnAddr);
77         if (!git->constantBound) {
78             parsing_printf("\t not a constant bound, skip\n");
79             continue;
80         }           
81
82         ParseAPI::Block *guardBlock = git->block;
83         // Note that the guardBlock and the srcBlock can be the same, 
84         // but since the conditional jump will always be the last instruction
85         // in the block, if they are in the same block, the src can reach the guard
86         if (src != Node::Ptr() && rf.incoming[guardBlock].find(srcBlock) == rf.incoming[guardBlock].end()) {
87             parsing_printf("\t this guard is not between the source block %lx and the target %lx, skip\n", srcBlock->start(), guardBlock->start());
88             continue;
89         }           
90         bool pred_taken = rf.branch_taken[guardBlock].find(trgBlock) != rf.branch_taken[guardBlock].end();
91         bool pred_ft = rf.branch_ft[guardBlock].find(trgBlock) != rf.branch_ft[guardBlock].end();
92         parsing_printf("pred_taken : %d, pred_ft: %d\n", pred_taken, pred_ft);
93         // If both branches reach the trg node, then this conditional jump 
94         // does not bound any variable for the trg node.
95         if (pred_taken ^ pred_ft) {
96             // Here I need to figure out which branch bounds the variable and 
97             // check it is the bounded path that reaches the trg node.
98             AST::Ptr cmpAST;
99             bool boundedOnTakenBranch = git->varSubtrahend ^ git->jumpWhenNoZF;
100             if (   (boundedOnTakenBranch && pred_taken)
101                 // In thic case, we jump when the variable is smaller than the constant.
102                 // So the condition taken path is the path that bounds the value.
103                 || (!boundedOnTakenBranch && pred_ft) ) {
104                 // In thic case, we jump when the variable is larger than the constant.
105                 // So the fallthrough path is the path that bounds the value.
106
107                 if (curFact->cmpBoundFactLive == false || git->cmpBound > curFact->cmpBound) {
108                     curFact->cmpAST = git->cmpAST;
109                     curFact->cmpBound = git->cmpBound;
110                     curFact->cmpBoundFactLive = true;
111                     curFact->cmpUsedRegs = git->usedRegs;
112                 }
113             }
114         }
115     }
116     if (!curFact->cmpBoundFactLive && firstBlock) {
117         // If this is indirect jump is in the first block,
118         // it is possible that it is a jump table for a function 
119         // with variable number of arguments. Then the convention
120         // is that al contains the number of argument.
121         MachRegister reg;
122         if (func->obj()->cs()->getAddressWidth() == 8) reg = x86_64::rax; else reg = x86::eax;
123         curFact->cmpAST = VariableAST::create(Variable(Absloc(reg)));
124         curFact->cmpBound = 8;
125         curFact->cmpUsedRegs.insert(reg);
126         curFact->cmpBoundFactLive = true;
127     }
128 }
129
130
131 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
132
133     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode); 
134     parsing_printf("Calculate Meet for %lx\n", node->addr());
135
136     NodeIterator gbegin, gend;
137     curNode->ins(gbegin, gend);    
138     BoundFact* newFact = new BoundFact();
139
140     if (gbegin != gend) {
141         bool first = true;      
142         for (; gbegin != gend; ++gbegin) {
143             SliceNode::Ptr meetSliceNode = boost::static_pointer_cast<SliceNode>(*gbegin); 
144             BoundFact *prevFact = GetBoundFact(*gbegin);            
145             if (prevFact == NULL) {
146                 parsing_printf("\tIncoming node %lx has not been calculated yet\n", meetSliceNode->addr());
147                 continue;
148             }
149             prevFact = new BoundFact(*prevFact);
150             parsing_printf("\tMeet incoming edge from %lx\n", meetSliceNode->addr());
151
152             ConditionalJumpBound(prevFact, *gbegin, curNode);
153             if (first) {
154                 first = false;
155                 *newFact = *prevFact;
156             } else {
157                 newFact->Intersect(*prevFact);
158             }
159             parsing_printf("New fact after the change is\n");
160             newFact->Print();
161
162         }
163     } else {
164         ConditionalJumpBound(newFact, Node::Ptr(), curNode);
165         parsing_printf("Meet no incoming nodes\n");
166         newFact->Print();
167     }
168     return newFact;
169 }
170
171 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
172
173     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
174     AbsRegion &ar = node->assign()->out();
175
176     parsing_printf("Expanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), node->assign()->insn()->format().c_str());
177     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
178
179     if (expandRet.first == NULL) {
180         // If the instruction is outside the set of instrutions we
181         // add instruction semantics. We assume this instruction
182         // kills all bound fact.
183         parsing_printf("\t No semantic support for this instruction. Kill all bound fact\n");
184         return;
185     }
186     parsing_printf("\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
187
188     AST::Ptr calculation = SimplifyAnAST(expandRet.first, node->assign()->insn()->size());
189
190     parsing_printf("\t AST after expanding %s\n", calculation->format().c_str());
191     parsing_printf("Calculating transfer function: Input facts\n");
192     newFact->Print();
193
194     BoundCalcVisitor bcv(*newFact);
195     calculation->accept(&bcv);
196
197     if (bcv.IsResultBounded(calculation)) { 
198         parsing_printf("Genenerate bound fact for %s\n", ar.absloc().format().c_str());
199         newFact->GenFact(ar.absloc(), new BoundValue(*bcv.GetResultBound(calculation)));
200     }
201     else {
202         parsing_printf("Kill bound fact for %s\n", ar.absloc().format().c_str());
203         newFact->KillFact(ar.absloc());
204     }
205     parsing_printf("Calculating transfer function: Output facts\n");
206     newFact->Print();
207
208 }                                               
209
210 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
211     auto fit = boundFacts.find(node);
212     if (fit == boundFacts.end())
213         return NULL;
214     else
215         return fit->second;
216 }
217
218 BoundFactsCalculator::~BoundFactsCalculator() {
219     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
220         if (fit->second != NULL)
221             delete fit->second;
222     boundFacts.clear();
223 }
224
225