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

[jlebar]

Summary

Also add a comment briefly explaining what ifcnv is.

No functional changes.

[resistor]

Why is this needed?

[jlebar]

In D17430#356755, @resistor wrote:

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.

[resistor]

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.

[jlebar]

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]

Just add comments explaining why current code is safe.

[resistor]

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.

[jlebar]

In D17430#357590, @resistor wrote:

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.

[resistor]

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.

[jlebar]

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...)

[jlebar]

Reverted in r261547. Sorry again for the trouble.

[jlebar]

New review in D17518.

llvm/trunk/lib/CodeGen/IfConversion.cpp

 //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements the machine instruction level if-conversion pass.
+// This file implements the machine instruction level if-conversion pass, which
+// tries to convert conditional branches into predicated instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
 #include "BranchFolding.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
void IfConverter::ScanInstructions(BBInfo &BBI) {
   BBI.ExtraCost = 0;
   BBI.ExtraCost2 = 0;
   BBI.ClobbersPred = false;
   for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
        I != E; ++I) {
     if (I->isDebugValue())
       continue;
 
+    // Don't need to check isConvergent(). It's OK to duplicate convergent
+    // instructions here, because we'll only push convergent operations up the
+    // CFG -- this can only *remove* control-flow dependencies.
     if (I->isNotDuplicable())
       BBI.CannotBeCopied = true;
 
     bool isPredicated = TII->isPredicated(I);
     bool isCondBr = BBI.IsBrAnalyzable && I->isConditionalBranch();
 
     // A conditional branch is not predicable, but it may be eliminated.
     if (isCondBr)