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