[InstCombine] Fold icmp into phi beyond the same BB.

[bipmis]

Summary

Observing cases where folding a icmp into phi can be beneficial. Particularly if the above fold results in the icmp argument of type BinaryOperator, it may enable more folding.
Need to understand if there is reason why the folding of icmp into phi happens within the same BB only.
Can this be done under additional checks.

Ran all tests. Looks Ok to me.

[bipmis]

Gentle Ping.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3895–3896

I don't think this special case make sense. Either we allow this, or we don't. There is no reason to believe that this is beneficial for just binary operators -- it just happens that this allows follow-on folds in your specific example.

I am open to dropping the check entirely, if we don't see any significant regressions from that.

[bipmis]

Updating the patch to fold cmp's into phi beyond BB.
Tested and did not find any significant regressions. Can provide the test results if needed.

[dmgreen]

My results agree - this seems to look OK perf wise.

[nikic]

LGTM, let's see if anyone complains.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3896–3897

You can just drop this comment -- not terribly helpful now that the check is gone. (We're folding not only beyond the same block.)

[nikic]

You might want to double check whether the dfsan failure in pre-merge checks is legitimate or not.

[bipmis]

Updating patch to handle the dfsan compiler-rt test case.

dfsan failure in pre-merge checks is legitimate. Looks like the first branch is being optimized out based on the proposed change. assert added to avoid it.
Additionally dfsan_set_label(LabelIJ..) has been added. This handles the original and latest changes in the code correctly. I could be wrong. Would be good to have check if the changes looks correct.

[browneee]

compiler-rt/test/dfsan/conditional_callbacks.c

100

Thanks nikic and bipmis for checking this change with me :)

The point of the test is that tainted_cond should have taint labels propagated from above. This change would invalidate this test, and break the behavior this is testing for.

I wonder, what is the IR for ((DataI * DataJ) != 1) before and after this change? I suspect this is where the taint label is being lost.

[bipmis]

compiler-rt/test/dfsan/conditional_callbacks.c

100

Ok Thanks for explaining it.
Let me discuss the IR for the original conditional_callbacks.c before and after the change.
I see the DataI and DataJ are obtained from argv as expected and same in both cases. The result calculation is completely avoided in the mod patch. The phi of the result values is also avoided. Instead it is converted to an i1 cmp based on the value check of DataJ==2.

The error I encounter with this is :
/home/bipmis01/llvm_30may/llvm-project/compiler-rt/test/dfsan/conditional_callbacks.c:79:12: error: CHECK: expected string not found in input
CHECK: Label 1 used as condition
<stdin>:1:1: note: scanning from here
conditional_callbacks.c.tmp: /home/bipmis01/llvm_30may/llvm-project/compiler-rt/test/dfsan/conditional_callbacks.c:35: void my_dfsan_conditional_callback(dfsan_label, dfsan_origin): Assertion `Label == LabelI' failed.//

[browneee]

compiler-rt/test/dfsan/conditional_callbacks.c

100

Thanks. Now that I see the error, my suspicion was wrong (or maybe that is a second problem after the error).

When dfsan is tracking tainted data, this feature allows users to find when the data is used to make a decision (ie, used in a control flow condition).

int DataI = (Argv[0][0] != 0) ? 1 : 0; // 69: no callback here, because condition is not tainted

if (DataI) { // 80: DataI was tainted by dfsan_set_label(LabelI, &DataI, sizeof(DataI));

Because DataI is tainted, my_dfsan_conditional_callback gets called.

static int Count = 0;
  switch (Count++) {

The Count in my_dfsan_conditional_callback is a hack to have different logic each time my_dfsan_conditional_callback.

The assert that is failing on 35, when Count==0. So the first call has a tainted condition (otherwise it wouldn't be called) but it is not tainted with LabelI.

The failure of Label != LabelI probably means that my_dfsan_conditional_callback is first called from another location.

if (DataI) { // 80

I think this code still happens (your diff; left 93 (IIUC, the left side of your diff is new?)), but later - so the calls to my_dfsan_conditional_callback would happen in a different order - and the assertions would fail.

I suggest temporarily remove the assertions in the switch in my_dfsan_conditional_callback, and see if it prints 3 things for the 3 // CHECK:. This would confirm things are still working, and the problem is that the test was not robust to code re-ordering.

[bipmis]

compiler-rt/test/dfsan/conditional_callbacks.c

100

I think the first condition has been optimised away.
./conditional_callbacks.c.tmp-orig FooBarBaz
Label 1 used as condition
Label 2 used as condition
Label 3 used as condition
Label 3 used as condition

./conditional_callbacks.c.tmp FooBarBaz
Label 2 used as condition
Label 3 used as condition

This can also be seen from the IR.
A modification to the test as below now works. Not right but just a proof of the calls taking place

switch (Count++) {
case 0:
  assert(Label == LabelJ);
  break;
case 1:
  assert(Label == LabelIJ);
  break;
default:
  break;
}

And remove the first check from source

// CHECK: Label 1 used as condition

[browneee]

compiler-rt/test/dfsan/conditional_callbacks.c

100

I think first condition being optimised away makes sense as an explanation, and matches that output.

Question is how to fix it?

Ideas

1. Mark dfsan_set_label second argument as volatile? I think this would prevent the optimization from removing the if.
2. Change the code in the test so the optimization won't break the test. e.g. maybe result = identity(42); where identity() is not inlined (I don't have a good sense for when optimizations will [not] occur).
3. Run DFSan transform pass earlier, before these optimizations? (maybe not feasible; probably a fair bit of work to figure out)

Re 1):

I think this is a problem here only because the (Argv[0][0] != 0) ? 1 : 0; ternary, the dfsan_set_label, and the if are all so close together. If dfsan_set_label was much earlier, then I expect the first ternary would trigger the check and it would work out ok.

Change would be

• https://github.com/llvm/llvm-project/blob/1034688d58783779168d59b47d2b3e897ad869c6/compiler-rt/include/sanitizer/dfsan_interface.h#L46
• https://github.com/llvm/llvm-project/blob/1034688d58783779168d59b47d2b3e897ad869c6/compiler-rt/lib/dfsan/dfsan.h#L31
• https://github.com/llvm/llvm-project/blob/1034688d58783779168d59b47d2b3e897ad869c6/compiler-rt/lib/dfsan/dfsan.cpp#L580

And similar surrounding functions.

This may be the best option, if it works.

Re 2):

It wouldn't surprise me if there are already other cases where a use in a condition is optimized away, and we just don't have a test pointing to it. Would prefer to keep the if condition (modified to avoid optimization) rather than remove it.

I'm OK with this option.

Re 3):

Probably much more effort than the other two. May create other problems.

[bipmis]

compiler-rt/test/dfsan/conditional_callbacks.c

100

Thanks for the ideas.

1. havent checked yet as it could involve changes to multiple files which uses dfsan_set_label. Also I am not fully sure if this would avoid the optimization from taking place.

2. Other way to avoid the optimization from happening is to use the value of result. In the current case since only use of result is an assert, it optimizes way most of it(condition1 ,the entire switch and assert itself). The simplest change can be a print of result every time it is updated.

I checked this and it works fine.
This would avoid any new flow/code changes and still avoid the optimization from kicking in. Let me know if this sounds OK. I can update the patch for you to have a look.
Thanks.

[browneee]

compiler-rt/test/dfsan/conditional_callbacks.c

100

Printing results SGTM. A non-inlined function to add things to result would probably work too. Thanks!

[bipmis]

Updated patch to use the result by prints. Avoids the optimization of conditions and passes the test.

[bipmis]

compiler-rt/test/dfsan/conditional_callbacks.c

100

Thanks. Have updated the patch.
Agreed that can work too.

[bipmis]

@browneee @nikic Please have a look and let me know if the test changes look OK. Thanks.

[dmgreen]

If this works and passes the test then it sounds good to me. LGTM

compiler-rt/test/dfsan/conditional_callbacks.c

int main(int Argc, char *Argv[]) {
   LabelIJ = dfsan_union(LabelI, LabelJ);
 
   assert(dfsan_get_label(DataI) == LabelI);
 
   // CHECK: Label 1 used as condition
   if (DataI) {
     result = 42;
   }
   
+  fprintf(stderr, "Result is %d\n", result);
   assert(dfsan_get_label(DataJ) == LabelJ);
 
   // CHECK: Label 2 used as condition
   switch (DataJ) {
   case 1:
     result += 10000;
     break;
   case 2:
     result += 4200;
     break;
   default:
     break;
   }
 
   int tainted_cond = ((DataI * DataJ) != 1);
+  fprintf(stderr, "Result is %d\n", result);
   assert(dfsan_get_label(tainted_cond) == LabelIJ);
 
   // CHECK: Label 3 used as condition
   result = tainted_cond ? result + 420000 : 9;
 
+  fprintf(stderr, "Result is %d\n", result);
   assert(result == 424242);
   return 0;
 }
 
 #endif // #ifdef CALLBACKS

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpInstWithConstantNotInt(ICmpInst &I) {
   case Instruction::GetElementPtr:
     // icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null
     if (RHSC->isNullValue() &&
         cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
       return new ICmpInst(
           I.getPredicate(), LHSI->getOperand(0),
           Constant::getNullValue(LHSI->getOperand(0)->getType()));
     break;
   case Instruction::PHI:
-    // Only fold icmp into the PHI if the phi and icmp are in the same
-    // block.  If in the same block, we're encouraging jump threading.  If
-    // not, we are just pessimizing the code by making an i1 phi.
-    if (LHSI->getParent() == I.getParent())
-      if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
-        return NV;
     break;
   case Instruction::IntToPtr:
     // icmp pred inttoptr(X), null -> icmp pred X, 0
     if (RHSC->isNullValue() &&
         DL.getIntPtrType(RHSC->getType()) == LHSI->getOperand(0)->getType())
       return new ICmpInst(
           I.getPredicate(), LHSI->getOperand(0),
           Constant::getNullValue(LHSI->getOperand(0)->getType()));
Instruction *InstCombinerImpl::visitFCmpInst(FCmpInst &I) {
   }
 
   // Handle fcmp with instruction LHS and constant RHS.
   Instruction *LHSI;
   Constant *RHSC;
   if (match(Op0, m_Instruction(LHSI)) && match(Op1, m_Constant(RHSC))) {
     switch (LHSI->getOpcode()) {
     case Instruction::PHI:
-      // Only fold fcmp into the PHI if the phi and fcmp are in the same
-      // block.  If in the same block, we're encouraging jump threading.  If
-      // not, we are just pessimizing the code by making an i1 phi.
-      if (LHSI->getParent() == I.getParent())
-        if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
-          return NV;
       break;
     case Instruction::SIToFP:
     case Instruction::UIToFP:
       if (Instruction *NV = foldFCmpIntToFPConst(I, LHSI, RHSC))
         return NV;
       break;
     case Instruction::FDiv:
       if (Instruction *NV = foldFCmpReciprocalAndZero(I, LHSI, RHSC))

llvm/test/Transforms/InstCombine/icmp-constant-phi.ll

 ; CHECK-LABEL: @test_ne_float(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi float [ 1.000000e+00, [[IF_TRUE]] ], [ 1.250000e+00, [[IF_FALSE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[COMPARE:%.*]] = fcmp one float [[PHI]], 1.250000e+00
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

 ; CHECK-LABEL: @test_ne_float_vector(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi <2 x float> [ <float 1.232500e+02, float 1.232500e+02>, [[IF_TRUE]] ], [ <float 4.562500e+02, float 4.562500e+02>, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi <2 x i1> [ <i1 false, i1 true>, [[IF_TRUE]] ], [ <i1 true, i1 false>, [[IF_FALSE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[COMPARE:%.*]] = fcmp one <2 x float> [[PHI]], <float 1.232500e+02, float 4.562500e+02>
-; CHECK-NEXT:    ret <2 x i1> [[COMPARE]]
+; CHECK-NEXT:    ret <2 x i1> [[PHI]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

llvm/test/Transforms/InstCombine/phi.ll

 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[_Z3FOOPKC_EXIT:%.*]], label [[WHILE_COND_I:%.*]]
 ; CHECK:       while.cond.i:
 ; CHECK-NEXT:    [[TEST_0_I:%.*]] = phi ptr [ [[INCDEC_PTR_I:%.*]], [[WHILE_COND_I]] ], [ [[VAL1]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[TEST_0_I]], align 1
 ; CHECK-NEXT:    [[CMP1_NOT_I:%.*]] = icmp eq i8 [[TMP0]], 0
 ; CHECK-NEXT:    [[INCDEC_PTR_I]] = getelementptr inbounds i8, ptr [[TEST_0_I]], i64 1
 ; CHECK-NEXT:    br i1 [[CMP1_NOT_I]], label [[WHILE_END_I:%.*]], label [[WHILE_COND_I]]
 ; CHECK:       while.end.i:
-; CHECK-NEXT:    [[SUB_PTR_LHS_CAST_I:%.*]] = ptrtoint ptr [[TEST_0_I]] to i64
-; CHECK-NEXT:    [[SUB_PTR_RHS_CAST_I:%.*]] = ptrtoint ptr [[VAL1]] to i64
-; CHECK-NEXT:    [[SUB_PTR_SUB_I:%.*]] = sub i64 [[SUB_PTR_LHS_CAST_I]], [[SUB_PTR_RHS_CAST_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne ptr [[TEST_0_I]], [[VAL1]]
 ; CHECK-NEXT:    br label [[_Z3FOOPKC_EXIT]]
 ; CHECK:       _Z3fooPKc.exit:
-; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i64 [ [[SUB_PTR_SUB_I]], [[WHILE_END_I]] ], [ 0, [[ENTRY]] ]
+; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i1 [ [[TMP1]], [[WHILE_END_I]] ], [ false, [[ENTRY]] ]
 ; CHECK-NEXT:    [[CMP_I10:%.*]] = icmp eq ptr [[VAL2:%.*]], null
 ; CHECK-NEXT:    br i1 [[CMP_I10]], label [[_Z3FOOPKC_EXIT20:%.*]], label [[WHILE_COND_I11:%.*]]
 ; CHECK:       while.cond.i11:
 ; CHECK-NEXT:    [[TEST_0_I12:%.*]] = phi ptr [ [[INCDEC_PTR_I14:%.*]], [[WHILE_COND_I11]] ], [ [[VAL2]], [[_Z3FOOPKC_EXIT]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[TEST_0_I12]], align 1
-; CHECK-NEXT:    [[CMP1_NOT_I13:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[TEST_0_I12]], align 1
+; CHECK-NEXT:    [[CMP1_NOT_I13:%.*]] = icmp eq i8 [[TMP2]], 0
 ; CHECK-NEXT:    [[INCDEC_PTR_I14]] = getelementptr inbounds i8, ptr [[TEST_0_I12]], i64 1
 ; CHECK-NEXT:    br i1 [[CMP1_NOT_I13]], label [[WHILE_END_I15:%.*]], label [[WHILE_COND_I11]]
 ; CHECK:       while.end.i15:
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne ptr [[TEST_0_I12]], [[VAL2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne ptr [[TEST_0_I12]], [[VAL2]]
 ; CHECK-NEXT:    br label [[_Z3FOOPKC_EXIT20]]
 ; CHECK:       _Z3fooPKc.exit20:
-; CHECK-NEXT:    [[RETVAL_0_I19:%.*]] = phi i1 [ [[TMP2]], [[WHILE_END_I15]] ], [ false, [[_Z3FOOPKC_EXIT]] ]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i64 [[RETVAL_0_I]], 0
-; CHECK-NEXT:    [[AND9:%.*]] = and i1 [[TOBOOL]], [[RETVAL_0_I19]]
+; CHECK-NEXT:    [[RETVAL_0_I19:%.*]] = phi i1 [ [[TMP3]], [[WHILE_END_I15]] ], [ false, [[_Z3FOOPKC_EXIT]] ]
+; CHECK-NEXT:    [[AND9:%.*]] = and i1 [[RETVAL_0_I]], [[RETVAL_0_I19]]
 ; CHECK-NEXT:    ret i1 [[AND9]]
 ;
 entry:
   %cmp.i = icmp eq ptr %val1, null
   br i1 %cmp.i, label %_Z3fooPKc.exit, label %while.cond.i
 
 while.cond.i:
   %test.0.i = phi ptr [ %incdec.ptr.i, %while.cond.i ], [ %val1, %entry ]