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 (x86Node node : dataflow 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) {

    auto LLVMBBs = node.getLLVMBB();
    for (auto LLVMBB : LLVMBBs) {
      retval.append(findCandidateLLVMNodesInBB(node, BB));
    }
    return retval;
  }

  if (some parents have no candidates) {
    //find the latest parents having candidate LLVM nodes
  }


  // 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) {
    for (each child of node) {
    if (isReachable(t, child)) {
      retval.append(t);
    }
  }

  return accumMatches;
}

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

  if(not reachable) {
    for (each child of node) {
      return isReachable(t, child);
  } else {
    return false;
  }
}