Chandler Carruth
2014-Aug-02 02:35 UTC
[LLVMdev] We have a pervasive problem in the SelectionDAG: the CSEMap.
There are a large number of places where we use pointer-identity for SDNodes through code paths which at times use ReplaceAllUsesWith. When coupled with the CSEMap which re-canonicalizes nodes at every step, this forms really bad ABA problems: we will often end up deleting a node because we build a new-but-identical node during RAUW. When this happens, the pointers cease to be valid and can lead to ABA. The RAUW code itself and the DAG combiner fix this by using a DAG Update Listener which snoops on all node deletions and tries to update every datastructure that might be holding an iterator or pointer key that has become invalidated. But there are a lot more datastructures key-ing on 'SDNode *' than there are DAG update listeners, so I suspect we have latent bugs here already. Does anyone have good ideas about how to solve this? I thought I did until I realized how fundamental the conflict is. I've now given up, but I wanted to raise the issue in case others are hitting it or have good ideas about how to get to a more predictable world. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140801/bcbbc719/attachment.html>
Evan Cheng
2014-Aug-02 17:25 UTC
[LLVMdev] We have a pervasive problem in the SelectionDAG: the CSEMap.
Yes, this is a problem. The only good long term solution, at least the one I am aware of, is to move away from SelectionDAG. Evan Sent from my iPad> On Aug 1, 2014, at 7:35 PM, Chandler Carruth <chandlerc at google.com> wrote: > > There are a large number of places where we use pointer-identity for SDNodes through code paths which at times use ReplaceAllUsesWith. When coupled with the CSEMap which re-canonicalizes nodes at every step, this forms really bad ABA problems: we will often end up deleting a node because we build a new-but-identical node during RAUW. When this happens, the pointers cease to be valid and can lead to ABA. > > The RAUW code itself and the DAG combiner fix this by using a DAG Update Listener which snoops on all node deletions and tries to update every datastructure that might be holding an iterator or pointer key that has become invalidated. But there are a lot more datastructures key-ing on 'SDNode *' than there are DAG update listeners, so I suspect we have latent bugs here already. > > Does anyone have good ideas about how to solve this? I thought I did until I realized how fundamental the conflict is. I've now given up, but I wanted to raise the issue in case others are hitting it or have good ideas about how to get to a more predictable world. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev