Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
ASTs are DAGs indeed, but as soon as you add semantic information to the mix the graph usually becomes cyclic.