I am sorry for this self-advertisement, but I am developing a tool here. My final goal is to recover the original control flow graph of virtualized binaries. But at a step of this, for visualization purpose, I have implemented a functionality to reconstruct the CFG of binaries from traces. The main implementation of this reconstrution is in the file
src/lib/cap/graph.cpp, it has no problem in performance in constructing the basic block graph from traces of about 100K instructions (I have tested on obfuscated binaries whose traces are about 300K instructions). You can see several pdf files in the folders
results, I have generated them from execution traces.
If you are interested in, I am more than happy to answer any further question.