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     if (FEPProb.find(addr) != FEPProb.end())
 320         return FEPProb[addr];
 321     unsigned char *buf = (unsigned char*)(cs->getPtrToInstruction(addr));
 322     if (!PassPreCheck(buf)) return 0;
 323 //    if (addr != 0x8049d68) return 0;
 324     double w = model.getBias();
 325     bool valid = true;
 326 //    fprintf(stderr, "before forward matching w = %.6lf\n", w);
 327     w += calcForwardWeights(0, addr, model.getNormalIdiomTreeRoot(), valid);
 328 //    fprintf(stderr, "after forward matching w = %.6lf\n", w);
 329
 330     if (valid) {
 331         set<IdiomPrefixTree*> matched;
 332         w += calcBackwardWeights(0, addr, model.getPrefixIdiomTreeRoot(), matched);
 333 //      fprintf(stderr, "after backward matching w = %.6lf\n", w);
 334
 335         double prob = ((double)1) / (1 + exp(-w));
 336         return FEPProb[addr] = reachingProb[addr] = prob;
 337     } else return FEPProb[addr] = reachingProb[addr] = 0;
 338 }
 339
 340 void ProbabilityCalculator::calcProbByEnforcingConstraints() {
 341
 342     // Initialize our knowledge about non-gap functions
 343     finalized.clear();
 344     for (auto fit = parser->obj().funcs().begin(); fit != parser->obj().funcs().end(); ++fit) {
 345         finalized.insert(*fit);
 346         for (auto bit = (*fit)->blocks().begin(); bit != (*fit)->blocks().end(); ++bit) {
 347             for (Address addr = (*bit)->start(); addr != (*bit)->end(); ++addr)
 348                 reachingProb[addr] = 2;
 349         }
 350     }
 351
 352     priority_queue<ProbAndAddr> q;
 353     double threshold = model.getProbThreshold();
 354     // Use the prob from matching idioms and push all the FEP candidates into the priority queue
 355     for (auto pit = FEPProb.begin(); pit != FEPProb.end(); ++pit)
 356         if (pit->second >= threshold)
 357             q.push(ProbAndAddr(pit->first, pit->second));
 358
 359     while (!q.empty()) {
 360         ProbAndAddr pa = q.top();
 361         q.pop();
 362
 363         //This is an out-dated item. The address has either improved prob by
 364         //applying call consistency constraints or 0 prob by applying overlapping constraints.
 365         if (double_cmp(FEPProb[pa.addr], pa.prob) != 0) continue;
 366
 367         parser->parse_at(cr, pa.addr, true, GAP);
 368
 369         Function *f = parser->findFuncByEntry(cr, pa.addr);
 370         assert(f != NULL);
 371
 372         fprintf(stderr, "Enforcing constraints at %lx with prob %.6lf\n", pa.addr, pa.prob);
 373         // Enforce the overlapping constraints
 374         dyn_hash_map<Address, double> newFEPProb, newReachingProb;
 375         dyn_hash_set<Function *> newDiscoveredFuncs;
 376         if (enforceOverlappingConstraints(f, pa.addr, pa.prob, newFEPProb, newReachingProb, newDiscoveredFuncs)) {
 377             Finalize(newFEPProb, newReachingProb, newDiscoveredFuncs);
 378             // Enforce the call consistency constraints
 379         } else {
 380             Remove(newDiscoveredFuncs);
 381         }
 382     }
 383
 384 }
 385
 386 double ProbabilityCalculator::getFEPProb(Address addr) {
 387     if (FEPProb.find(addr) != FEPProb.end()) return FEPProb[addr];
 388     return 0;
 389 }
 390
 391 double ProbabilityCalculator::getReachingProb(Address addr) {
 392     if (reachingProb.find(addr) != reachingProb.end()) return reachingProb[addr];
 393     return 0;
 394 }
 395
 396 bool ProbabilityCalculator::isFEP(Address addr) {
 397     double prob = getFEPProb(addr);
 398     if (prob >= model.getProbThreshold()) return true; else return false;
 399 }
 400
 401 double ProbabilityCalculator::calcForwardWeights(int cur, Address addr, IdiomPrefixTree *tree, bool &valid) {
 402     if (addr >= cr->high()) return 0;
 403 //    printf("Start matching at %lx for %dth idiom term\n", addr, cur);
 404
 405     double w = 0;
 406     if (tree->isFeature()) w = tree->getWeight();
 407
 408     if (tree->isLeafNode()) return w;
 409
 410     DecodeData data;
 411     if (!decodeInstruction(data, addr)) {
 412         valid = false;
 413         return 0;
 414     }
 415
 416     const IdiomPrefixTree::ChildrenType* children = tree->getChildrenByEntryID(data.entry_id);
 417     if (children != NULL) {
 418         for (auto cit = children->begin(); cit != children->end() && valid; ++cit)
 419             if (cit->first.match(IdiomTerm(cit->first.entry_id, data.arg1, data.arg2))) {
 420                 w += calcForwardWeights(cur + 1, addr + data.len, cit->second, valid);
 421             }
 422     }
 423     if (!valid) return 0;
 424     // Wildcard terms also match the current instruction
 425     children = tree->getWildCardChildren();
 426     if (children != NULL) {
 427         // Note that for a wildcard term,
 428         // there is no need to really check whether the operands match or not,
 429         // but at least we know that the current address can
 430         // be decoded into a valid instruction.
 431         for (auto cit = children->begin(); cit != children->end() && valid; ++cit)
 432             w += calcForwardWeights(cur + 1, addr + data.len, cit->second, valid);
 433     }
 434
 435     // the return value is not important if "valid" becomes false
 436     return w;
 437 }
 438
 439 double ProbabilityCalculator::calcBackwardWeights(int cur, Address addr, IdiomPrefixTree *tree, set<IdiomPrefixTree*> &matched) {
 440     double w = 0;
 441     if (tree->isFeature()) {
 442         if (matched.find(tree) == matched.end()) {
 443             matched.insert(tree);
 444             w += tree->getWeight();
 445 //          fprintf(stderr, "Backward match idiom with weight %.6lf\n", tree->getWeight());
 446         }
 447     }
 448 //    printf("Start matching at %lx for %dth idiom term\n", addr, cur);
 449
 450     if (tree->isLeafNode()) return w;
 451
 452     for (Address prevAddr = addr - 1; prevAddr >= cr->low() && addr - prevAddr <= 15; --prevAddr) {
 453         DecodeData data;
 454         if (!decodeInstruction(data, prevAddr)) continue;
 455         if (prevAddr + data.len != addr) continue;
 456
 457         // Look for idioms that match the exact current instruction
 458         const IdiomPrefixTree::ChildrenType* children = tree->getChildrenByEntryID(data.entry_id);
 459         if (children != NULL) {
 460             for (auto cit = children->begin(); cit != children->end(); ++cit)
 461                 if (cit->first.match(IdiomTerm(cit->first.entry_id, data.arg1, data.arg2))) {
 462                     w += calcBackwardWeights(cur + 1, prevAddr , cit->second, matched);
 463                 }
 464         }
 465         // Wildcard terms also match the current instruction
 466         children = tree->getWildCardChildren();
 467         if (children != NULL) {
 468             for (auto cit = children->begin(); cit != children->end(); ++cit)
 469                 w += calcBackwardWeights(cur + 1, prevAddr , cit->second, matched);
 470         }
 471
 472     }
 473     return w;
 474 }
 475
 476 bool ProbabilityCalculator::decodeInstruction(DecodeData &data, Address addr) {
 477     DecodeCache::iterator iter = decodeCache.find(addr);
 478     if (iter != decodeCache.end()) {
 479         data = iter->second;
 480         if (data.len == 0) return false;
 481     } else {
 482         unsigned char *buf = (unsigned char*)(cs->getPtrToInstruction(addr));
 483         if (buf == NULL) {
 484             decodeCache.insert(make_pair(addr, DecodeData(JUNK_OPCODE, 0,0,0)));
 485             return false;
 486         }
 487         InstructionDecoder dec( buf ,  30, cs->getArch());
 488         Instruction::Ptr insn = dec.decode();
 489         if (!insn) {
 490             decodeCache.insert(make_pair(addr, DecodeData(JUNK_OPCODE, 0,0,0)));
 491             return false;
 492         }
 493         data.len = insn->size();
 494         if (data.len == 0) {
 495             decodeCache.insert(make_pair(addr, DecodeData(JUNK_OPCODE, 0,0,0)));
 496             return false;
 497         }
 498
 499         const Operation & op = insn->getOperation();
 500         data.entry_id = op.getID();
 501
 502         vector<Operand> ops;
 503         insn->getOperands(ops);
 504         int args[2] = {NOARG,NOARG};
 505         for(unsigned int i=0;i<2 && i<ops.size();++i) {
 506             Operand & op = ops[i];
 507             if (op.getValue()->size() == 0) {
 508                 // This is actually an invalid instruction with valid opcode
 509                 // so modify the opcode cache to make it invalid
 510                 decodeCache.insert(make_pair(addr, DecodeData(JUNK_OPCODE, 0,0,0)));
 511                 return false;
 512             }
 513
 514             if(!op.readsMemory() && !op.writesMemory()) {
 515                 // register or immediate
 516                 set<RegisterAST::Ptr> regs;
 517                 op.getReadSet(regs);
 518                 op.getWriteSet(regs);
 519
 520                 if(!regs.empty()) {
 521                     if (regs.size() > 1) {
 522                         args[i] = MULTIREG;
 523                     } else {
 524                         args[i] = (*regs.begin())->getID();
 525                     }
 526                 } else {
 527                     // immediate
 528                     args[i] = IMMARG;
 529                 }
 530             } else {
 531                 args[i] = MEMARG;
 532             }
 533         }
 534         data.arg1 = args[0];
 535         data.arg2 = args[1];
 536         decodeCache.insert(make_pair(addr, data));
 537     }
 538     return true;
 539 }
 540
 541
 542
 543 bool ProbabilityCalculator::enforceOverlappingConstraints(Function *f,
 544                                                           Address cur_addr,
 545                                                           double cur_prob,
 546                                                           dyn_hash_map<Address, double> &newFEPProb,
 547                                                           dyn_hash_map<Address, double> &newReachingProb,
 548                                                           dyn_hash_set<Function*> &newDiscoveredFuncs) {
 549     // Only apply the overlapping constraints to un-finalized functions
 550     if (finalized.find(f) != finalized.end()) return true;
 551     if (newDiscoveredFuncs.find(f) != newDiscoveredFuncs.end()) return true;
 552     newDiscoveredFuncs.insert(f);
 553     fprintf(stderr,"  in function at %lx\n", f->addr());
 554     for (auto bit = f->blocks().begin(); bit != f->blocks().end(); ++bit) {
 555         if ((*bit)->region() != cr) continue;
 556         fprintf(stderr, "  block [%lx,%lx)\n", (*bit)->start(), (*bit)->end());
 557         for (Address addr = (*bit)->start(); addr < (*bit)->end(); ++addr) {
 558
 559             // Meet a byte that is in a function with higher probability: conflict
 560             if (double_cmp(cur_prob, getReachingProb(addr)) < 0) {
 561                 fprintf(stderr, "    conflict with %lx with reaching prob %.6lf\n", addr, getReachingProb(addr));
 562                 return false;
 563             } else if (double_cmp(cur_prob, getReachingProb(addr)) > 0) {
 564                 newReachingProb[addr] = cur_prob;
 565                 newFEPProb[addr] = 0;
 566             } else {
 567                 // TODO: meet a byte with same prob
 568             }
 569         }
 570     }
 571
 572     auto call_edges = f->callEdges();
 573     for (auto eit = call_edges.begin(); eit != call_edges.end(); ++eit) {
 574         if ((*eit)->type() == CALL_FT) continue;
 575         Address target = (*eit)->trg()->start();
 576         if (reachingProb.find(target) == reachingProb.end()) continue;
 577         if (double_cmp(cur_prob, getFEPProb(target)) > 0) {
 578             newFEPProb[target] = cur_prob;
 579         }
 580         if (double_cmp(cur_prob, getReachingProb(target)) > 0){
 581             newReachingProb[target] = cur_prob;
 582         }
 583         Function *callee = parser->findFuncByEntry(cr, target);
 584 //      fprintf(stderr, "    find call target from %lx to %lx\n", (*eit)->src()->last(), target);
 585         if (callee == NULL) {
 586             parser->parse_at(cr, target, true, GAP);
 587             callee = parser->findFuncByEntry(cr, target);
 588 //          assert(callee != NULL);
 589         }
 590         if (callee == NULL) continue;
 591         if (!enforceOverlappingConstraints(callee, cur_addr, cur_prob, newFEPProb, newReachingProb, newDiscoveredFuncs)) return false;
 592     }
 593     return true;
 594 }
 595
 596 void ProbabilityCalculator::Finalize(dyn_hash_map<Address, double> &newFEPProb,
 597                                      dyn_hash_map<Address, double> &newReachingProb,
 598                                      dyn_hash_set<Function*> &newDiscoveredFuncs) {
 599     for (auto nit = newFEPProb.begin(); nit != newFEPProb.end(); ++nit) {
 600         FEPProb[nit->first] = nit->second;
 601     }
 602     for (auto nit = newReachingProb.begin(); nit != newReachingProb.end(); ++nit) {
 603         reachingProb[nit->first] = nit->second;
 604     }
 605     finalized.insert(newDiscoveredFuncs.begin(), newDiscoveredFuncs.end());
 606 }
 607
 608 void ProbabilityCalculator::Remove(dyn_hash_set<Function*> &newDiscoveredFuncs) {
 609     for (auto fit = newDiscoveredFuncs.begin(); fit != newDiscoveredFuncs.end(); ++fit) {
 610        parser->remove_func(*fit);
 611     }
 612 }
 613
 614 void ProbabilityCalculator::prioritizedGapParsing() {
 615     priority_queue<ProbAndAddr> q;
 616     double threshold = model.getProbThreshold();
 617
 618     // Use the prob from matching idioms and push all the FEP candidates into the priority queue
 619     for (auto pit = FEPProb.begin(); pit != FEPProb.end(); ++pit)
 620         if (pit->second >= threshold)
 621             q.push(ProbAndAddr(pit->first, pit->second));
 622
 623     while (!q.empty()) {
 624         ProbAndAddr pa = q.top();
 625         q.pop();
 626         parser->parse_at(cr, pa.addr, true, GAP);
 627
 628     }
 629
 630 }
 631 #endif
 632