On Mon, Nov 09, 2020 at 01:47:24PM -0800, Linus Torvalds wrote: > On Mon, Nov 9, 2020 at 1:16 PM Luc Van Oostenryck > <luc.vanoostenryck@xxxxxxxxx> wrote: > > > > There is no phi-source here and the CBR at .L3 could be merged > > with the one at .L0, removing the false imbalance but it's not. > > I thought that sparse was doing this sort of branch simplification > > but it doesn't, or at least it doesn't in this (simple) situation. > > The branch rewriting sparse does is very simplistic, afaik. It's also > confusingly written. I blame myself. > > Honestly, in that example you quote: > > cbr %arg1, .L1, .L2 > .L1: context 1 > br .L3 > .L2: call use, %r1 > br .L3 > .L3: cbr %arg1, .L5, .L4 ;; false imbalance here > > we never even try to combine the two cbr's, because they don't jump > directly to each other. > > I think it would be easy to simplify if we just added some logic to > change "unconditional branch to conditional branch", and moved the cbr > up into L1 and L2, but I don't think we have any such logic (and it's > a simplification that might end up being the opposite of a > simplification - it would duplicate the conditional). > > So we could try to remove L3 entirely, by moving it into both parents: > > cbr %arg1, .L1, .L2 > .L1: context 1 > cbr %arg1, .L5, .L4 > .L2: call use, %r1 > cbr %arg1, .L5, .L4 Mmm yes, I see. > and at that point, the branch simplification we *do* have woudl see > that both of those duplicated conditional branches are now dominated > by the first one, and we'd end up with > > cbr %arg1, .L1, .L2 > .L1: context 1 > br .L5 > .L2: call use, %r1 > br .L4 > > and then we'd join L2 and L4 together and the end result would look nice. I was simply thinking doing this directly. In the case of a simple 'diamond' (with the top and bottom CBR on the same conditional), there is no dependency/dominance problems and it's enough to change the target of the BR in the two side BBs. > But as it stands now, L3 isn't dominated by one side of the original > conditional branch (because we reach L3 from both sides), and the cbr > in L3 isn't something we can simplify without duplicating it and > moving it up into the parents. > > Is duplicating the conditional branch worth it? In this case, clearly > yes. But in general? Maybe we could do it in cases like this, when the > *only* thing in a basic block is that conditional branch. I think the general solution is to look at the dominance tree: if there is another conditional branch with the same condition and which dominates the current, then it must be safe to duplicate because it can be simplified away anyway. Otherwise, I would prefer to avoid duplicating anything without some cost/benefit guarantee. -- Luc
