This patch adds function findNearestCommonDominatorInst that, for a given
set of instructions, finds their nearest dominating instruction.
As an alternative implementation, have you considered teaching DomTree::findNCD to work with multiple basic blocks first, and then using this to implement the multi-instruction findNCD?
The algorithm would be like this: create a vector VBB of BB of all instructions, find its NCD, case split on the NCD and VBB being the same block or not.
Does this work for invoke instructions? I'm thinking of a situation when two instructions are in a block whose immediate dominator ends with an invoke but the invoke result is not available for these two instructions.
I was considering that, but don't really see how it's useful. The existing code makes N iterations, for which of them it either calls comesBefore or findNCD (findNCD will be called as many times as many different blocks there is - 1).
In the proposed solution, I'll need to:
- FIll the set of blocks (because API of findNCD needs blocks)
- Call multi-arg findNCD (which will call two-arg NCD same amount of times)
- make comesBefore queries for all instructions in topmost block.
Effectively it's always the same number of findNCD queries, overhead on set creation and potentially less number of comesBefore queries (in my solution we do it in all blocks). So overhead on set filling doesn't seem worth saving some number of cheap comesBefore queries in general case. So I just don't see why this alternative solution is better.
I was thinking more in terms of API design, not algorithmic efficiency. To me it seems like there's a clear boundary between block-level and instruction-level analysis here and I propose to separate the concerns more if this doesn't complicate the implementation. I think that finding the NCD of multiple blocks should be useful by itself; there was even a question about it on llvm-dev fairly recently: https://groups.google.com/g/llvm-dev/c/TZ3MCpwO5Yg/m/Z4MfZz_jBAAJ.
I'd find it very surprising if the result of findNCDInst returned an instruction that didn't dominate an argument.
Note that dominates is defined above as:
/// In particular, it is worth noting that: /// * Non-instruction Defs dominate everything. /// * Def does not dominate a use in Def itself (outside of degenerate cases /// like unreachable code or trivial phi cycles). /// * Invoke/callbr Defs only dominate uses in their default destination. bool dominates(const Value *Def, const Use &U) const;
As I understand this function is not about def and use at all while in the doc you mentioned it is about def-use chain.
And why do you think that result of this function does not dominate any of arguments? It does to my understanding if consider this as an extension of Basic Block domination definition.
Does it make sense to explicitly mention in the doc function that it is not about def-use chain but about instructions and use an example with invoke to emphasize it to avoid confusion and incorrect usage of this utility function?
Yeah, you are right.
By 'an argument' I meant any instruction in Insns, not the type Argument.
I got tripped of that this generalizes some existing function that checks if an instruction dominates another instruction. But now that you pointed out that the two-argument dominates operates on instructions and *uses*, I see that this is not the case.
Where do you plan to use findNCDInst? I'm trying to understand why bool dominates(Inst, Inst) and Inst findNCDInst(Inst, Inst) haven't been used before.
What do you think about defining and implementing bool dominates(Inst, Inst) at the same time (or before) findNCDInst? IMO it's awkward to explain what finding the NCD of instructions means without first defining dominance between instructions. Then you can use that definition as a post-condition for findNCDInst and check that the result dominates all Insns. Similarly, I'd also implement findNCD for multiple blocks first and then use it in the version for instructions. Otherwise I'd see it as building something very specific without laying out all the foundations first.
It will have a signature clash with existing dominates(def, use). For that, we first need to rename existing dominates (including all its users across the code) into something like defUseAvailable, and only then implement this. It's a massive refactoring of whole DomTree which I definitely don't want to be blocked on. As you see, as set of changes is currently waiting for this patch.
We can make this, but separately, as follow-up, after the changes are unblocked, if it makes sense.
dominates(def, use) has a slightly different semantics and fails for dominates(x, x). I also think ther will be tricky corner cases when it will fail when both args are Phis from the same block.
I see the deep API problem here now. Current dominates(Value *, Instruction *) should not be called like that (at least because it returns false for dominates(X, X)). It has a different semantics, and should be called something like "canBeUserOf".
The clear definition of dominance between two instructions is also something fishy. Specifically, it is fishy for Phi nodes from the same block (there is no precedence between them). Maybe the best name to express what we need in this patch would be comesBefore.
It looks like a vast rework of whole DomTree API. I'm OK doing that, but do not want to have my patches waiting for this API rework (they honestly don't need). Let's unblock this branch first and then think how to name it better.
I see three ways forward:
- Propose the renaming of the existing .dominates functions on llvm-dev and to that before this work.
- Add instruction-level dominance function, but call it differently to avoid name collision, e.g., dominatesInst. Use this in this revision and propose refactoring afterwards.
- Implement findNCDInst as a free function where it's actually necessary. Maybe this notion of dominance and NCD of instructions is domain-specific enough that there's not much value in adding this to DominatorTree?
I'd be most comfortable with (2) or (3).