This is an archive of the discontinued LLVM Phabricator instance.

[ifcnv] Add comment explaining why it's OK to duplicate convergent MIs in ifcnv.
ClosedPublic

Authored by jlebar on Feb 18 2016, 5:49 PM.

Diff Detail

Event Timeline

jlebar updated this revision to Diff 48441.Feb 18 2016, 5:49 PM
jlebar retitled this revision from to [ifcvn] Don't duplicate blocks containing convergent instructions..
jlebar updated this object.
jlebar added a reviewer: echristo.
jlebar added subscribers: llvm-commits, tra.
resistor edited edge metadata.Feb 18 2016, 9:11 PM

Why is this needed?

Why is this needed?

AIUI, if CannotBeCopied is false (the default), IfConverter is free to duplicate code as it moves it around. That's not safe in general for convergent ops -- that's where I was coming from when I wrote the patch.

However, inasmuch as we always move convergent ops *up* the CFG, I guess this is OK -- we're only subtracting control-flow dependencies. But it's not at all clear to me that's what's happening here.

If-conversion doesn't change the control dependencies of the MIs that it moves. It just changes the expression of the dependency from expression via branches to expression via predication. Either way, the execution of the convergent op is still gated by the same set of expressions. Hence, I don't think any change is needed here.

It just changes the expression of the dependency from expression via branches to expression via predication.

Aha, thank you. I definitely didn't understand this.

I'll update this patch to add some comments, hopefully save the next person some time.

jlebar updated this revision to Diff 48554.Feb 19 2016, 3:59 PM
jlebar edited edge metadata.

Just add comments explaining why current code is safe.

jlebar retitled this revision from [ifcvn] Don't duplicate blocks containing convergent instructions. to [ifcnv] Add comment explaining why it's OK to duplicate convergent MIs in ifcnv..Feb 19 2016, 3:59 PM
jlebar updated this object.
jlebar updated this object.

I don't agree with the new comments. If conversion does not remove any dependencies. It just changes their expression from control flow to predication, but they're still control dependencies in that they gate execution.

I don't agree with the new comments. If conversion does not remove any dependencies. It just changes their expression from control flow to predication, but they're still control dependencies in that they gate execution.

My understanding is that it's a bit more complicated than that. I'm looking at the "simple" transformation, and afaict, if the basic block we're predicating has more than one predecessor, we copy it into one predecessor (adding predication) and also leave it alone so it can still be branched to. It's specifically this sort of thing that I'm trying to say is safe.

To be concrete, suppose we have

BB1 --> TBB
BB2 --> (TBB or FBB) based on cond
TBB --> exit

The simple conversion on the BB2 + TBB + FBB subgraph will convert this to

BB1 --> TBB --> exit
BB2 --> predicated (TBB + exit) --> FBB

In this case a convergent operation inside TBB originally had a CFG dependency equal to BB1 || BB2+cond. After the transform there are two convergent instructions, one with a dependency equal to BB1, and the other with a dependency equal to BB2+cond. I read this as "removing" a control-flow dependency on the two instructions, but maybe that's not the right way to express what's going on.

It's quite likely I'm still misunderstanding what's going on here. Once we settle on an understanding I'll definitely update the comment, since it's either wrong or unclear.

Thank you for your help.

Ok, I see what you're trying to get at, and I agree with your assessment that a it is removing a control dependence. Since it's specific to exactly the transform being applied, I think a little deeper explanation in the comment is merited.

This revision was automatically updated to reflect the committed changes.

Shoot, I had a git fail and committed this accidentally. I'm about to revert.

(I guess I really do need to spend a few days making better tools for this workflow...)

Reverted in r261547. Sorry again for the trouble.

New review in D17518.