1. A wildcard term should only match one instruction (improve quality)
[dyninst.git] / parseAPI / src / ProbabilisticParser.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #if defined(cap_stripped_binaries)
32
33 #include <cstdio>
34 #include <cmath>
35 #include <algorithm>
36 #include <queue>
37 #include <iostream>
38
39 #include "entryIDs.h"
40 #include "dyn_regs.h"
41 #include "InstructionDecoder.h"
42 #include "Instruction.h"
43
44 #include "ProbabilisticParser.h"
45
46 using namespace std;
47 using namespace Dyninst;
48 using namespace Dyninst::ParseAPI;
49 using namespace Dyninst::InstructionAPI;
50 using namespace NS_x86;
51 using namespace hd; 
52
53
54 // Precision error allowed in double precision float number
55 #define ZERO 1e-8
56 static int double_cmp(double a, double b) {
57     double delta = a - b;
58     if (fabs(delta) < ZERO) return 0;
59     else if (delta > ZERO) return 1;
60     else return -1;
61 }
62
63 struct ProbAndAddr {
64     Address addr;
65     double prob;
66
67     ProbAndAddr(Address a, double p): addr(a), prob(p) {}
68     bool operator < (const ProbAndAddr &p) const {
69         if (double_cmp(prob, p.prob) == 0) return addr > p.addr;
70         return prob < p.prob;
71     }
72 };
73 static bool MatchArgs(unsigned short arg1, unsigned short arg2) {
74     return arg1 == arg2;
75 }
76
77 bool IdiomTerm::match(const IdiomTerm &it) const {    
78     if (entry_id == WILDCARD_ENTRY_ID || it.entry_id == WILDCARD_ENTRY_ID) return true; // Wildcard matches everything
79     if (entry_id == e_nop && it.entry_id == e_nop) return true; // Nops match without considering arguments
80     if (entry_id != it.entry_id) return false;
81     return MatchArgs(arg1, it.arg1) && MatchArgs(arg2, it.arg2);
82 }
83
84 bool IdiomTerm::matchOpcode(unsigned short eid) const {
85     if (entry_id == WILDCARD_ENTRY_ID || eid == WILDCARD_ENTRY_ID) return true; // Wildcard matches everything
86     return entry_id == eid;
87 }
88
89 bool IdiomTerm::operator == (const IdiomTerm &it) const {
90     return (entry_id == it.entry_id) && (arg1 == it.arg1) && (arg2 == it.arg2);
91 }
92
93 bool IdiomTerm::operator < (const IdiomTerm &it) const {
94     if (entry_id != it.entry_id) return entry_id < it.entry_id;
95     if (arg1 != it.arg1) return arg1 < it.arg1;
96     return arg2 < it.arg2;
97 }
98
99 static string HandleAnOperand(unsigned short arg, int style) {
100     if(arg != NOARG) {
101         if (arg == MEMARG) {
102             if (style) return "MEM"; else return ":A";
103         }
104         else if (arg == IMMARG) {
105             if (style) return "IMM"; else return ":B";
106         }
107         else if (arg == MULTIREG) {
108             if (style) return "MULTIREG"; else return ":C";
109         }
110         else if (arg == CALLEESAVEREG) {
111             if (style) return "Callee saved reg"; else return ":D";
112         } 
113         else if (arg == ARGUREG) {
114             if (style) return "Argu passing reg"; else return ":E";
115         }
116         else if (arg == OTHERREG) {
117             if (style) return "Other reg"; else return ":F";
118         }
119         else {
120             // the human_readble format is still broken
121             if (style) {
122                 if (arg == 0x0010) return x86_64::rip.name();
123                 switch (arg & 0xf000) {
124                     case 0x0000:
125                         //GPR
126                         return MachRegister(arg | x86_64::GPR | Arch_x86_64).name();
127                     case 0x1000:
128                         //mmx
129                         return MachRegister(arg | x86_64::MMX | Arch_x86_64).name();
130                     case 0x2000:
131                         //xxm
132                         return MachRegister(arg | x86_64::XMM | Arch_x86_64).name();
133                     case 0x4000:
134                         // flag bit
135                         return MachRegister(arg | x86_64::FLAG | Arch_x86_64).name();
136                 }
137
138               
139                 return ":" + MachRegister(arg).name();
140             }
141             char buf[64];
142             snprintf(buf, 64, "%x", arg);
143             return string(":") + string(buf);
144         }
145     }
146     return "";
147 }
148
149
150 string IdiomTerm::human_format() const {
151     string entryname;
152     if(*this == WILDCARD_TERM)
153         entryname = "*";
154     else if(entryNames_IAPI.find((entryID)(entry_id)) == entryNames_IAPI.end()) {
155         entryname = "[UNMAPED]";
156         fprintf(stderr, "Found entryID not mapped in entryNames_IAPI %d\n", entry_id);
157     }
158     else {
159         entryname = entryNames_IAPI[(entryID)(entry_id)];
160         if (arg1 != NOARG) entryname += " " + HandleAnOperand(arg1, 1);
161         if (arg2 != NOARG) entryname += "," + HandleAnOperand(arg2, 1);
162     }
163
164     return entryname;        
165
166 }
167
168 bool Idiom::operator < (const Idiom &i) const {
169     if (terms.size() != i.terms.size()) return terms.size() < i.terms.size();
170     for (size_t index = 0; index < terms.size(); ++index)
171         if (terms[index] < i.terms[index]) return true;
172         else if (i.terms[index] < terms[index]) return false;
173     return false;
174 }
175
176 static void split(const char * str, vector<uint64_t> & terms)
177 {
178     const char *s = str, *e = NULL;
179     char buf[32];
180     
181     while((e = strchr(s,'_')) != NULL) {
182         assert(e-s < 32);
183         strncpy(buf,s,e-s);
184         buf[e-s] = '\0';
185
186 #if defined (os_windows)
187 #define dyn_strtoull _strtoui64
188 #else
189 #define dyn_strtoull strtoull
190 #endif
191         terms.push_back(dyn_strtoull(buf,NULL,16));
192         
193         s = e+1;
194     }
195     // last one
196     if(strlen(s)) {
197         terms.push_back(dyn_strtoull(s,NULL,16));
198     }
199 #undef dyn_strtoull
200 }
201 Idiom::Idiom(string format, double weight, bool pre): 
202     w(weight), prefix(pre)
203 {
204     vector<uint64_t> items;
205     split(format.c_str(), items);
206
207     unsigned short entry_id, arg1, arg2;
208     for (size_t i = 0; i < items.size(); ++i) {
209         uint64_t t = items[i];
210         if(!(t & ENTRY_MASK)) {
211             t = t << ARG_SIZE;
212             t |= NOARG;
213         }
214         if(!(t & ENTRY_MASK)) {
215             t = t << ARG_SIZE;
216             t |= NOARG;
217         }
218         
219         entry_id = (t>>32) & 0xffffffff;
220         arg1 = (t>>16) & 0xffff;
221         arg2 = t & 0xffff;
222         terms.push_back(IdiomTerm(entry_id, arg1, arg2));
223
224     }
225     if (prefix) reverse(terms.begin(), terms.end());       
226 }
227
228 string Idiom::human_format() const {
229     string ret = "";
230
231     //printf("formatting %s\n",format().c_str());
232     for(unsigned i=0;i<terms.size();++i) {
233         ret += terms[i].human_format();
234         if(i<terms.size()-1)
235             ret += "|";
236     }
237     return ret;
238
239 }
240
241 IdiomPrefixTree::IdiomPrefixTree() {
242     feature = false;
243 }
244
245 void IdiomPrefixTree::addIdiom(const Idiom& idiom) {
246     addIdiom(0, idiom);
247 }
248
249 void IdiomPrefixTree::addIdiom(int cur, const Idiom& idiom) {
250     if (cur == (int)idiom.terms.size()) {
251         feature = true;
252         w = idiom.w;
253     } else {
254         ChildrenByEntryID::iterator idit = childrenClusters.find(idiom.terms[cur].entry_id);
255         if (idit == childrenClusters.end()) {
256             idit = childrenClusters.insert(make_pair(idiom.terms[cur].entry_id,ChildrenType())).first;
257         }
258         ChildrenType& children = idit->second;
259         ChildrenType::iterator next = children.end();
260         for (auto cit = children.begin(); cit != children.end(); ++cit) {
261             if (cit->first == idiom.terms[cur]) {
262                 next = cit;
263                 break;
264             }
265         }
266
267         if (next == children.end()) {
268             children.push_back(make_pair(idiom.terms[cur], new IdiomPrefixTree() ) );
269             next = children.end();
270             --next;
271         }
272         next->second->addIdiom(cur+1, idiom);
273     }
274 }
275
276 bool IdiomPrefixTree::findChildrenWithOpcode(unsigned short entry_id, ChildrenType &ret) {
277     ChildrenByEntryID::iterator idit = childrenClusters.find(entry_id);
278     if (idit != childrenClusters.end()) {
279         ret.insert(ret.end(), idit->second.begin(), idit->second.end());
280     }
281     idit = childrenClusters.find(WILDCARD_ENTRY_ID);
282     if (idit != childrenClusters.end()) {
283         ret.insert(ret.end(), idit->second.begin(), idit->second.end());
284     } 
285     return !ret.empty();
286 }
287
288 bool IdiomPrefixTree::findChildrenWithArgs(unsigned short arg1, unsigned short arg2, const ChildrenType &candidate, ChildrenType &ret) {
289     for (auto cit = candidate.begin(); cit != candidate.end(); ++cit) {
290         if (cit->first.match(IdiomTerm(cit->first.entry_id, arg1, arg2)))
291             ret.push_back(*cit);
292     }
293     return !ret.empty();
294 }
295
296 const IdiomPrefixTree::ChildrenType* IdiomPrefixTree::getChildrenByEntryID(unsigned short entry_id) {
297     ChildrenByEntryID::iterator iter = childrenClusters.find(entry_id);
298     if (iter == childrenClusters.end())
299         return NULL;
300     else
301         return &iter->second;
302 }
303 const IdiomPrefixTree::ChildrenType* IdiomPrefixTree::getWildCardChildren() {
304     return getChildrenByEntryID(WILDCARD_ENTRY_ID);
305 }
306 ProbabilityCalculator::ProbabilityCalculator(CodeRegion *reg, CodeSource *source, Parser* p, string model_spec):
307     model(model_spec), cr(reg), cs(source), parser(p) 
308 {
309 }
310
311 static bool PassPreCheck(unsigned char *buf) {
312     if (buf == NULL) return false;
313     if (*buf == 0 || *buf == 0x90) return false;
314     return true;
315 }
316
317 double ProbabilityCalculator::calcProbByMatchingIdioms(Address addr) {
318     unsigned char *buf = (unsigned char*)(cs->getPtrToInstruction(addr));
319     if (!PassPreCheck(buf)) return 0;
320 //    if (addr != 0x8049d68) return 0;
321     double w = model.getBias();
322     bool valid = true;
323 //    fprintf(stderr, "before forward matching w = %.6lf\n", w);
324     w += calcForwardWeights(0, addr, model.getNormalIdiomTreeRoot(), valid);
325 //    fprintf(stderr, "after forward matching w = %.6lf\n", w);
326
327     if (valid) {
328         set<IdiomPrefixTree*> matched;
329         w += calcBackwardWeights(0, addr, model.getPrefixIdiomTreeRoot(), matched);
330 //      fprintf(stderr, "after backward matching w = %.6lf\n", w);
331
332         double prob = ((double)1) / (1 + exp(-w));
333         return FEPProb[addr] = reachingProb[addr] = prob;       
334     } else return FEPProb[addr] = reachingProb[addr] = 0;
335 }
336
337 void ProbabilityCalculator::calcProbByEnforcingConstraints() {
338
339     // Initialize our knowledge about non-gap functions
340     finalized.clear();
341     for (auto fit = parser->obj().funcs().begin(); fit != parser->obj().funcs().end(); ++fit) {    
342         finalized.insert(*fit);
343         for (auto bit = (*fit)->blocks().begin(); bit != (*fit)->blocks().end(); ++bit) {
344             for (Address addr = (*bit)->start(); addr != (*bit)->end(); ++addr)
345                 reachingProb[addr] = 2;
346         }
347     }
348
349     priority_queue<ProbAndAddr> q;
350     double threshold = model.getProbThreshold();
351     // Use the prob from matching idioms and push all the FEP candidates into the priority queue
352     for (auto pit = FEPProb.begin(); pit != FEPProb.end(); ++pit)
353         if (pit->second >= threshold) 
354             q.push(ProbAndAddr(pit->first, pit->second));
355     
356     while (!q.empty()) {
357         ProbAndAddr pa = q.top();
358         q.pop();
359
360         //This is an out-dated item. The address has either improved prob by
361         //applying call consistency constraints or 0 prob by applying overlapping constraints.
362         if (double_cmp(FEPProb[pa.addr], pa.prob) != 0) continue;
363
364         parser->parse_at(cr, pa.addr, true, GAP);
365
366         Function *f = parser->findFuncByEntry(cr, pa.addr);
367         assert(f != NULL);
368
369         fprintf(stderr, "Enforcing constraints at %lx with prob %.6lf\n", pa.addr, pa.prob);
370         // Enforce the overlapping constraints
371         dyn_hash_map<Address, double> newFEPProb, newReachingProb;
372         dyn_hash_set<Function *> newDiscoveredFuncs;
373         if (enforceOverlappingConstraints(f, pa.addr, pa.prob, newFEPProb, newReachingProb, newDiscoveredFuncs)) {
374             Finalize(newFEPProb, newReachingProb, newDiscoveredFuncs);
375             // Enforce the call consistency constraints
376         } else {
377             Remove(newDiscoveredFuncs);
378         }
379     }
380
381 }
382
383 double ProbabilityCalculator::getFEPProb(Address addr) {
384     if (FEPProb.find(addr) != FEPProb.end()) return FEPProb[addr];
385     return 0;
386 }
387
388 double ProbabilityCalculator::getReachingProb(Address addr) {
389     if (reachingProb.find(addr) != reachingProb.end()) return reachingProb[addr];
390     return 0;
391 }
392
393 bool ProbabilityCalculator::isFEP(Address addr) {
394     double prob = getFEPProb(addr);
395     if (prob >= model.getProbThreshold()) return true; else return false;
396 }
397
398 double ProbabilityCalculator::calcForwardWeights(int cur, Address addr, IdiomPrefixTree *tree, bool &valid) {
399     if (addr >= cr->high()) return 0;
400 //    printf("Start matching at %lx for %dth idiom term\n", addr, cur);
401
402     double w = 0;
403     if (tree->isFeature()) w = tree->getWeight();
404
405     if (tree->isLeafNode()) return w;
406     
407
408     unsigned short entry_id, len;
409     if (!getOpcode(entry_id, len, addr)) {
410         valid = false;
411         return 0;
412     }
413
414 //    printf("  decode entry_id %x\n", entry_id);
415     // Look for idioms that match the exact current instruction
416     const IdiomPrefixTree::ChildrenType* children = tree->getChildrenByEntryID(entry_id);
417     if (children != NULL) {
418         unsigned short arg1, arg2;
419         if (!getArgs(arg1, arg2, addr)) {
420             valid = false;
421             return 0;
422         }
423         for (auto cit = children->begin(); cit != children->end() && valid; ++cit)
424             if (cit->first.match(IdiomTerm(cit->first.entry_id, arg1, arg2))) {
425                 w += calcForwardWeights(cur + 1, addr + len, cit->second, valid);
426             }
427     }
428     if (!valid) return 0;
429     // Wildcard terms also match the current instruction
430     children = tree->getWildCardChildren();
431     if (children != NULL) {
432         // Note that for a wildcard term,
433         // there is no need to really check whether the operands match or not,
434         // but at least we need to know that the current address can
435         // be decoded into a valid instruction.
436         unsigned short arg1, arg2;
437         if (!getArgs(arg1, arg2, addr)) {
438             valid = false;
439             return 0;
440         }
441         for (auto cit = children->begin(); cit != children->end() && valid; ++cit)
442             w += calcForwardWeights(cur + 1, addr + len, cit->second, valid);
443     }
444            
445     // the return value is not important if "valid" becomes false
446     return w;
447 }
448
449 double ProbabilityCalculator::calcBackwardWeights(int cur, Address addr, IdiomPrefixTree *tree, set<IdiomPrefixTree*> &matched) {
450     double w = 0;
451     if (tree->isFeature()) {
452         if (matched.find(tree) == matched.end()) {
453             matched.insert(tree);
454             w += tree->getWeight();
455 //          fprintf(stderr, "Backward match idiom with weight %.6lf\n", tree->getWeight());
456         }
457     }
458 //    printf("Start matching at %lx for %dth idiom term\n", addr, cur);
459
460     if (tree->isLeafNode()) return w;
461
462     for (Address prevAddr = addr - 1; prevAddr >= cr->low() && addr - prevAddr <= 15; --prevAddr) {
463         unsigned short entry_id, len;
464         if (!getOpcode(entry_id, len, prevAddr)) continue;
465         if (prevAddr + len != addr) continue;
466
467         // Look for idioms that match the exact current instruction
468         const IdiomPrefixTree::ChildrenType* children = tree->getChildrenByEntryID(entry_id);
469         if (children != NULL) {
470             unsigned short arg1, arg2;
471             if (!getArgs(arg1, arg2, prevAddr)) continue;
472             for (auto cit = children->begin(); cit != children->end(); ++cit)
473                 if (cit->first.match(IdiomTerm(cit->first.entry_id, arg1, arg2))) {
474                     w += calcBackwardWeights(cur + 1, prevAddr , cit->second, matched);
475                 }
476         }
477         // Wildcard terms also match the current instruction
478         children = tree->getWildCardChildren();
479         if (children != NULL) {
480             unsigned short arg1, arg2;
481             if (!getArgs(arg1, arg2, prevAddr)) continue;
482             for (auto cit = children->begin(); cit != children->end(); ++cit)
483                 w += calcBackwardWeights(cur + 1, prevAddr , cit->second, matched);
484         }
485
486     }
487     return w;
488 }
489
490 bool ProbabilityCalculator::getOpcode(unsigned short &entry_id, unsigned short &len, Address addr) {
491     MatchingCache::iterator iter = opcodeCache.find(addr);
492     if (iter != opcodeCache.end()) {
493         entry_id = iter->second.first;
494         len = iter->second.second;
495         if (len == 0) return false;
496     } else {
497         Instruction::Ptr insn;
498         unsigned char *buf = (unsigned char*)(cs->getPtrToInstruction(addr));
499         if (buf == NULL) { 
500             opcodeCache.insert(make_pair(addr, make_pair(JUNK_OPCODE, 0)));
501             return false;
502         }
503         InstructionDecoder dec( buf ,  30, cs->getArch()); 
504         insn = dec.decode();
505         if (!insn) {
506             opcodeCache.insert(make_pair(addr, make_pair(JUNK_OPCODE, 0)));
507             return false;
508         }
509         len = insn->size();
510         if (len == 0) {
511             opcodeCache.insert(make_pair(addr, make_pair(JUNK_OPCODE, 0)));
512             return false;
513         }
514         
515         const Operation & op = insn->getOperation();
516         entry_id = op.getID();
517         opcodeCache.insert(make_pair(addr, make_pair(entry_id, len)));
518     }    
519     return true;
520 }
521
522 bool ProbabilityCalculator::getArgs(unsigned short &arg1, unsigned short &arg2, Address addr) {
523     if (operandCache.find(addr) != operandCache.end()) {
524         const pair<unsigned short, unsigned short> &val = operandCache[addr];
525         arg1 = val.first;
526         arg2 = val.second;
527     } else {
528         Instruction::Ptr insn;   
529         unsigned char *buf = (unsigned char*)(cs->getPtrToInstruction(addr));
530         assert(buf != NULL);
531         
532         InstructionDecoder dec( buf ,  30, cs->getArch()); 
533         insn = dec.decode();
534         assert(insn);
535
536         vector<Operand> ops;
537         insn->getOperands(ops);
538         int args[2] = {NOARG,NOARG};
539         for(unsigned int i=0;i<2 && i<ops.size();++i) {
540             Operand & op = ops[i];
541             if (op.getValue()->size() == 0) {
542                 // This is actually an invalid instruction with valid opcode
543                 // so modify the opcode cache to make it invalid
544                 opcodeCache[addr] = make_pair(JUNK_OPCODE, 0);
545                 return false;
546             }
547
548             if(!op.readsMemory() && !op.writesMemory()) {
549                 // register or immediate
550                 set<RegisterAST::Ptr> regs;
551                 op.getReadSet(regs);
552                 op.getWriteSet(regs);  
553                 
554                 if(!regs.empty()) {
555                     if (regs.size() > 1) {
556                         args[i] = MULTIREG;
557                     } else {
558                         args[i] = (*regs.begin())->getID();
559                     }
560                 } else {
561                     // immediate
562                     args[i] = IMMARG;
563                 }
564             } else {
565                 args[i] = MEMARG; 
566             }
567         }
568         arg1 = args[0];
569         arg2 = args[1];
570         operandCache[addr] = make_pair(arg1, arg2);
571     }
572     return true;
573 }
574
575 bool ProbabilityCalculator::enforceOverlappingConstraints(Function *f, 
576                                                           Address cur_addr, 
577                                                           double cur_prob,
578                                                           dyn_hash_map<Address, double> &newFEPProb,
579                                                           dyn_hash_map<Address, double> &newReachingProb,
580                                                           dyn_hash_set<Function*> &newDiscoveredFuncs) {
581     // Only apply the overlapping constraints to un-finalized functions
582     if (finalized.find(f) != finalized.end()) return true;    
583     if (newDiscoveredFuncs.find(f) != newDiscoveredFuncs.end()) return true;
584     newDiscoveredFuncs.insert(f);
585     fprintf(stderr,"  in function at %lx\n", f->addr());
586     for (auto bit = f->blocks().begin(); bit != f->blocks().end(); ++bit) {       
587         if ((*bit)->region() != cr) continue;
588         fprintf(stderr, "  block [%lx,%lx)\n", (*bit)->start(), (*bit)->end());
589         for (Address addr = (*bit)->start(); addr < (*bit)->end(); ++addr) {
590
591             // Meet a byte that is in a function with higher probability: conflict
592             if (double_cmp(cur_prob, getReachingProb(addr)) < 0) {
593                 fprintf(stderr, "    conflict with %lx with reaching prob %.6lf\n", addr, getReachingProb(addr));
594                 return false;
595             } else if (double_cmp(cur_prob, getReachingProb(addr)) > 0) {
596                 newReachingProb[addr] = cur_prob;
597                 newFEPProb[addr] = 0;
598             } else {
599                 // TODO: meet a byte with same prob
600             }
601         }
602     }
603     
604     auto call_edges = f->callEdges();
605     for (auto eit = call_edges.begin(); eit != call_edges.end(); ++eit) {
606         if ((*eit)->type() == CALL_FT) continue;
607         Address target = (*eit)->trg()->start();
608         if (reachingProb.find(target) == reachingProb.end()) continue;
609         if (double_cmp(cur_prob, getFEPProb(target)) > 0) {
610             newFEPProb[target] = cur_prob;
611         }
612         if (double_cmp(cur_prob, getReachingProb(target)) > 0){
613             newReachingProb[target] = cur_prob;
614         }
615         Function *callee = parser->findFuncByEntry(cr, target);
616 //      fprintf(stderr, "    find call target from %lx to %lx\n", (*eit)->src()->last(), target);
617         if (callee == NULL) {
618             parser->parse_at(cr, target, true, GAP);
619             callee = parser->findFuncByEntry(cr, target);
620 //          assert(callee != NULL);  
621         }
622         if (callee == NULL) continue;
623         if (!enforceOverlappingConstraints(callee, cur_addr, cur_prob, newFEPProb, newReachingProb, newDiscoveredFuncs)) return false;
624     }
625     return true;
626 }
627
628 void ProbabilityCalculator::Finalize(dyn_hash_map<Address, double> &newFEPProb,
629                                      dyn_hash_map<Address, double> &newReachingProb,
630                                      dyn_hash_set<Function*> &newDiscoveredFuncs) {
631     for (auto nit = newFEPProb.begin(); nit != newFEPProb.end(); ++nit) {
632         FEPProb[nit->first] = nit->second;
633     }
634     for (auto nit = newReachingProb.begin(); nit != newReachingProb.end(); ++nit) {
635         reachingProb[nit->first] = nit->second;
636     }
637     finalized.insert(newDiscoveredFuncs.begin(), newDiscoveredFuncs.end());
638 }
639
640 void ProbabilityCalculator::Remove(dyn_hash_set<Function*> &newDiscoveredFuncs) {
641     for (auto fit = newDiscoveredFuncs.begin(); fit != newDiscoveredFuncs.end(); ++fit) {
642        parser->remove_func(*fit); 
643     }
644 }
645
646 void ProbabilityCalculator::prioritizedGapParsing() {
647     priority_queue<ProbAndAddr> q;
648     double threshold = model.getProbThreshold();
649
650     // Use the prob from matching idioms and push all the FEP candidates into the priority queue
651     for (auto pit = FEPProb.begin(); pit != FEPProb.end(); ++pit)
652         if (pit->second >= threshold) 
653             q.push(ProbAndAddr(pit->first, pit->second));
654     
655     while (!q.empty()) {
656         ProbAndAddr pa = q.top();
657         q.pop();
658         parser->parse_at(cr, pa.addr, true, GAP);
659
660     }
661
662 }
663 #endif
664