Change to store pointers to BoundValue rather than BoundValue objects in std::map...
[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     queue<Node::Ptr> workingList;
20
21     NodeIterator nbegin, nend;
22     slice->allNodes(nbegin, nend);
23
24     for (; nbegin != nend; ++nbegin) {
25         workingList.push(*nbegin);
26     }
27
28
29     while (!workingList.empty()) {
30         Node::Ptr curNode = workingList.front();
31         workingList.pop();
32
33         BoundFact* oldFact = GetBoundFact(curNode);
34         BoundFact* newFact = Meet(curNode);
35         CalcTransferFunction(curNode, newFact);
36
37         if (oldFact == NULL || *oldFact != *newFact) {
38             if (oldFact != NULL) delete oldFact;
39             boundFacts[curNode] = newFact;
40             curNode->outs(nbegin, nend);
41             for (; nbegin != nend; ++nbegin)
42                 workingList.push(*nbegin);
43         }
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         parsing_printf("Checking guard at %lx\n", git->jmpInsnAddr);
70         if (!git->constantBound) {
71             parsing_printf("\t not a constant bound, skip\n");
72             continue;
73         }           
74
75         ParseAPI::Block *guardBlock = git->block;
76         // Note that the guardBlock and the srcBlock can be the same, 
77         // but since the conditional jump will always be the last instruction
78         // in the block, if they are in the same block, the src can reach the guard
79         if (src != Node::Ptr() && rf.incoming[guardBlock].find(srcBlock) == rf.incoming[guardBlock].end()) {
80             parsing_printf("\t this guard is not between the source block %lx and the target %lx, skip\n", srcBlock->start(), guardBlock->start());
81             continue;
82         }           
83         bool pred_taken = rf.branch_taken[guardBlock].find(trgBlock) != rf.branch_taken[guardBlock].end();
84         bool pred_ft = rf.branch_ft[guardBlock].find(trgBlock) != rf.branch_ft[guardBlock].end();
85         parsing_printf("pred_taken : %d, pred_ft: %d\n", pred_taken, pred_ft);
86         // If both branches reach the trg node, then this conditional jump 
87         // does not bound any variable for the trg node.
88         if (pred_taken ^ pred_ft) {
89             // Here I need to figure out which branch bounds the variable and 
90             // check it is the bounded path that reaches the trg node.
91             AST::Ptr cmpAST;
92             bool boundedOnTakenBranch = git->varSubtrahend ^ git->jumpWhenNoZF;
93             if (   (boundedOnTakenBranch && pred_taken)
94                 // In thic case, we jump when the variable is smaller than the constant.
95                 // So the condition taken path is the path that bounds the value.
96                 || (!boundedOnTakenBranch && pred_ft) ) {
97                 // In thic case, we jump when the variable is larger than the constant.
98                 // So the fallthrough path is the path that bounds the value.
99
100                 if (curFact->cmpBoundFactLive == false || git->cmpBound > curFact->cmpBound) {
101                     curFact->cmpAST = git->cmpAST;
102                     curFact->cmpBound = git->cmpBound;
103                     curFact->cmpBoundFactLive = true;
104                     curFact->cmpUsedRegs = git->usedRegs;
105                 }
106             }
107         }
108     }
109     if (!curFact->cmpBoundFactLive && firstBlock) {
110         // If this is indirect jump is in the first block,
111         // it is possible that it is a jump table for a function 
112         // with variable number of arguments. Then the convention
113         // is that al contains the number of argument.
114         curFact->cmpAST = VariableAST::create(Variable(Absloc(x86_64::rax)));
115         curFact->cmpBound = 8;
116         curFact->cmpUsedRegs.insert(x86_64::rax);
117         curFact->cmpBoundFactLive = true;
118     }
119 }
120
121
122 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
123
124     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode); 
125     parsing_printf("Calculate Meet for %lx\n", node->addr());
126
127     NodeIterator gbegin, gend;
128     curNode->ins(gbegin, gend);    
129     BoundFact* newFact = new BoundFact();
130
131     if (gbegin != gend) {
132         bool first = true;      
133         for (; gbegin != gend; ++gbegin) {
134             SliceNode::Ptr meetSliceNode = boost::static_pointer_cast<SliceNode>(*gbegin); 
135             BoundFact *prevFact = GetBoundFact(*gbegin);            
136             if (prevFact == NULL) {
137                 parsing_printf("\tIncoming node %lx has not been calculated yet\n", meetSliceNode->addr());
138                 continue;
139             }
140             prevFact = new BoundFact(*prevFact);
141             parsing_printf("\tMeet incoming edge from %lx\n", meetSliceNode->addr());
142
143             ConditionalJumpBound(prevFact, *gbegin, curNode);
144             if (first) {
145                 first = false;
146                 *newFact = *prevFact;
147             } else {
148                 newFact->Intersect(*prevFact);
149             }
150             parsing_printf("New fact after the change is\n");
151             newFact->Print();
152
153         }
154     } else {
155         ConditionalJumpBound(newFact, Node::Ptr(), curNode);
156         parsing_printf("Meet no incoming nodes\n");
157         newFact->Print();
158     }
159     return newFact;
160 }
161
162 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
163
164     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
165     AbsRegion &ar = node->assign()->out();
166
167     parsing_printf("Expanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), node->assign()->insn()->format().c_str());
168     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
169
170     if (expandRet.first == NULL) {
171         // If the instruction is outside the set of instrutions we
172         // add instruction semantics. We assume this instruction
173         // kills all bound fact.
174         parsing_printf("\t No semantic support for this instruction. Kill all bound fact\n");
175         return;
176     }
177     parsing_printf("\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
178
179     AST::Ptr calculation = SimplifyAnAST(expandRet.first, node->assign()->insn()->size());
180
181     parsing_printf("\t AST after expanding %s\n", calculation->format().c_str());
182     parsing_printf("Calculating transfer function: Input facts\n");
183     newFact->Print();
184
185     BoundCalcVisitor bcv(*newFact);
186     calculation->accept(&bcv);
187
188     if (bcv.IsResultBounded(calculation)) { 
189         parsing_printf("Genenerate bound fact for %s\n", ar.absloc().format().c_str());
190         newFact->GenFact(ar.absloc(), new BoundValue(*bcv.GetResultBound(calculation)));
191     }
192     else {
193         parsing_printf("Kill bound fact for %s\n", ar.absloc().format().c_str());
194         newFact->KillFact(ar.absloc());
195     }
196     parsing_printf("Calculating transfer function: Output facts\n");
197     newFact->Print();
198
199 }                                               
200
201 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
202     auto fit = boundFacts.find(node);
203     if (fit == boundFacts.end())
204         return NULL;
205     else
206         return fit->second;
207 }
208
209 BoundFactsCalculator::~BoundFactsCalculator() {
210     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
211         if (fit->second != NULL)
212             delete fit->second;
213     boundFacts.clear();
214 }
215
216