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