I am writing a pass that requires the DominatorTree pass. In the runOnFunction of my own pass, I call llvm::SplitBlock to split a block (%for.end) at it’s first insert point. Then, when I dump my dominator tree immediately after, I can see the newly split %for.end.split, but its DFSNumIn and DFSNumOut are not properly updated in llvm::SplitBlock (i.e., still the initialized -1). At the same time, the DT->dump() results also show that DFSInfoValid equals false! I could not figure out what I did wrong, b/c it seems all the analysis updating should be handled by llvm::SplitBlock. Any suggestions on how to approach this situation? Thanks a bunch in advance.
------------------------- The actual dump of my dominator tree after SplitBlock --------------------
I am writing a pass that requires the DominatorTree pass. In the runOnFunction of my own pass, I call llvm::SplitBlock to split a block (%for.end) at it’s first insert point. Then, when I dump my dominator tree immediately after, I can see the newly split %for.end.split, but its DFSNumIn and DFSNumOut are not properly updated in llvm::SplitBlock (i.e., still the initialized -1). At the same time, the DT->dump() results also show that DFSInfoValid equals false! I could not figure out what I did wrong, b/c it seems all the analysis updating should be handled by llvm::SplitBlock. Any suggestions on how to approach this situation? Thanks a bunch in advance.
Hi Paul,
DFSNumbers is a cache within the DominatorTree analysis. It is lazily computed after a certain number of queries. It’s kind of hard to incrementally update these numbers because we may have to shift them all.
At any rate, invalid DFS numbers does not mean something is wrong with the analysis.
Thanks a lot. But the function “DT->dominate(A,B)” decides the dominance relationship through comparing the DFS numbers, right? At least, in my example, when I check whether the newly split node (i.e., %for.end.split) DOMINATES the original node (I.e., %for.end), the answer is true, which is obviously wrong.
Thanks a lot. But the function “DT->dominate(A,B)” decides the dominance relationship through comparing the DFS numbers, right? At least, in my example, when I check whether the newly split node (i.e., %for.end.split) DOMINATES the original node (I.e., %for.end), the answer is true, which is obviously wrong.
That sounds like a bug. When DFSInfoValid==false, the DFS number does not affect the query. So I don’t know why you’re getting the wrong answer.
I know you don’t have a test case, but I suggest filling a bugzilla PR and attaching a dump of both your IR and Domtree before splitting and after splitting.
As it turns out, it was my own mistake. I added a couple of BBs, and forgot to perform “DT->addNewBlock” on them. Still, in the situation where CFG gets modified, the behavior of the DominatorTree is counter-intuitive to what LLVM newbies expected to find … you would think that DT keeps track of how CFG is being modified, and perform analysis updates on-the-fly automatically. Thanks a lot for the help.
As it turns out, it was my own mistake. I added a couple of BBs, and forgot to perform “DT->addNewBlock” on them. Still, in the situation where CFG gets modified, the behavior of the DominatorTree is counter-intuitive to what LLVM newbies expected to find … you would think that DT keeps track of how CFG is being modified, and perform analysis updates on-the-fly automatically. Thanks a lot for the help.
It would be nice to have robust incremental updates behind a simple API. It’s the kind of thing that doesn’t get worked on because it’s too easy to rerun DT analysis when needed.