Graph Matching: Algorithm

/* Node stucture of x86-data-flow graph*/
struct x86Node {
  NodeInfo nodeInfo;
  vector<x86Node> parents;
};

/* Variable Matching Info*/
class VarBBMatcher {
private:
  map<x86Node, set<MatchedInfo>> _var_matches;
  map<x86BB, set<LLVM::BasicBlock>> _bb_matches;

public:
  struct MatchedInfo {
    LLVMNode candidate;
    int confidence;
  };

  static void addMatchingInfo(x86Node node, vector<MatchedInfo> info) {
    for (auto i : info) {
      _var_matches[node].insert(i);
      _bb_matches[node->parent].insert(i.parent);
    }
  }

  // Returns the LLVM basic block used for searching the LLVM varibales
  // corresponding to x86Node node.
  // Return values: If the parent x86 BB of node is Entry, then return the
  // coresponding entry LLVM BB.
  // Else return all the yet unmatched LLVM BBs
  vector<LLVM::BasicBlock> getLLVMBB(x86Node node);
};

/*
  main_driver is responsible for matching the data-flow
  sub-graphs for each instruction in x86 code
*/
void main_driver(x86Code code /*The x86 code*/) {
  for (each instruction I : Instruction in code(following the control flow)) {
    for (each node :
         x86Node of the data - flow graph of I in topological order) {
      matchNode(node)
    }
  }
}

void matchNode(x86Node node) {
  if (Matches.exists(node) == false) {
    VarBBMatcher.addMatchingInfo(node,
                                 findCandidateLLVMNodes(node, node.parents));
  }
}

typedef vector<LLVMNode> tuple;
MatchedInfo findCandidateLLVMNodes(x86Node node, vector<x86Node> parents) {
  set<MatchedInfo> retval;

  if (parents.size() == 0) { // No parents

    auto LLVMBBs = node.getLLVMBB();
    for (auto LLVMBB : LLVMBBs) {
      retval.append(findCandidateLLVMNodesInBB(node, BB));
    }
  } else {
    // If 'node' has n parents and each having O(m) LLVM node candidates,
    // then explore all the nm candidate tuples to check which ones has a path
    // to node
    for (each candidate tuple `t` of parents) {
      if (isReachable(t, node)) {
        retval.append(t);
      }
    }
  }

  return accumMatches;
}

/*
  Return true if each of the members of tuple t can reach a
  LLVM node corresponding to x86 node node.
*/
bool isReachable(tuple t, x86Node node) {


}