Devang Patel wrote: > On Jun 6, 2007, at 7:19 PM, Nick Lewycky wrote: > >>Predicate simplifier uses this to get the DFS nums for a BB. We also >>pass around ETNode*s to avoid having a lot of functions doing BB- >> >>>ETNode >> >>lookups. > > I am not familiar with predicate simplifier implementation, but why do > such look ups ? > > I am exploring the idea to make ETNode completely private unless there > is a good reason. Usually, a transformation needs dominance info, > it does not matter whether ETNode or DomTreeNode or SomeOtherNode is > used as part of DomTree or ETForest or SomeJungle to get that info.
The data structure that predsimplify really needs is a dominator tree with depth first search numberings on every block. Currently we simulate that by combining both the DominatorTree and ETForest passes. I chose what gets passed around based on performance. For example, if you need both a BasicBlock * and a DominatorTree::Node, pass the DTNode around because you can convert it to the BB in O(1) while converting a BB to DTNode takes a map lookup. Similarly, I pass ETNodes around to functions that don't care about which BB is actually involved, but do need the DFS numbers for whatever reason. This is very pervasive; in my dev tree, ETNode is mentioned in 38 lines of code in predsimplify, mostly function parameters. Six lines of code do lookups turning blocks into ETNodes. If we passed around BasicBlock* instead, there would need to be an additional 32 places that perform BB->ETNode lookups. One of those would be inside the comparison operator used to sort some vectors. In other words, it would almost certainly be a performance disaster. >>Similarly with updateDFSNumbers. More than a performance issue, if the >>DFS nums aren't up to date predsimplify will crash (and if it didn't >>crash it wouldn't work; it needs correct DFS nums). I spoke with Dan >>Berlin about it and he says that there's no guarantee that the DFS >>nums >>will be up to date upon entry to a pass, so I call it there. > > If you're interested then the simple way is to invoke > updateDFSNumbers() after each pass that claims that it preserves dom > info. Ok. Passes that don't access DFS numbers directly (every pass except predsimplify) would take a small performance hit as ETForest updates the numberings. That doesn't make it wrong though. Nick _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits