[InstCombine] Propagate null values from conditions to other basic blocks

[xbolva00]

Summary

Clang currectly generates longer and slower code for:
if (!ptr)

return ptr;

than for:
if (!ptr)

return NULL;

Code example: https://godbolt.org/g/wtimXj

This patch fixes it.

[lebedev.ri]

High-level question: what is this trying to do?
Can't you just use ReplaceUsesOfWith(), or something like that?

lib/Transforms/InstCombine/InstructionCombining.cpp

2399

Just cast<>

2400

I thought it is written somewhere, but i can't find it in https://llvm.org/docs/ProgrammersManual.html
TLDR: don't use auto unless the type is already obvious (or it is an iterator/etc).

This should be something like

auto *Cmp = dyn_cast<CmpInst>(BI.getOperand(0));
???? *NullOp = Cmp->getOperand(0);

2403

I'd expect this to be something closer to

for(??? *B = TrueDest; B != nullptr; B = B->getNextNode()) {

2404

Similarly, i have no clue what this is,

for (Instr &I : *B) {

?

2405

I'd try to use range-based loop, if there is a function to go from the pointer to an index, or setOperand() would work with index.

test/Transforms/InstCombine/cond-return-null.ll

18 ↗

(On Diff #141373)

Do you edit the check-lines after llvm/utils/update_test_checks.py?
Don't. (the first line included)

[xbolva00]

In D45378#1060001, @lebedev.ri wrote:

High-level question: what is this trying to do?
Can't you just use ReplaceUsesOfWith(), or something like that?

if (!ptr)

return NULL;

replaces e.g. $null with $ptr in blocks where we know $ptr == $null.

I have to rework patch, since it should jump to "NullPtrBlock" (after cmp) and then check br instr a jump to next possible block. Now, it just iterates over blocks starting with "NullPtrBlock".

[lebedev.ri]

Note that such a transform (null propagation) is already being done somewhere. https://godbolt.org/g/ow79c8
I'd recommend to first look where that is happening, and extend that, not introduce a duplicate-but-better fold elsewhere.

[spatel]

This is pushing instcombine beyond local simplifications. Propagating values across blocks should probably be handled in CVP (-correlated-propagation).

[xbolva00]

In D45378#1060146, @lebedev.ri wrote:

Note that such a transform (null propagation) is already being done somewhere. https://godbolt.org/g/ow79c8
I'd recommend to first look where that is happening, and extend that, not introduce a duplicate-but-better fold elsewhere.

But it does not work in basic case.. https://godbolt.org/g/wtimXj

[xbolva00]

In D45378#1060239, @spatel wrote:

This is pushing instcombine beyond local simplifications. Propagating values across blocks should probably be handled in CVP (-correlated-propagation).

Maybe, but here it also fits, every info required for this transformation is available here.

Implementation of this optimization would probably be quite massive in the CorrelatedValuePropagation.

[lebedev.ri]

In D45378#1060265, @xbolva00 wrote:

In D45378#1060146, @lebedev.ri wrote:

Note that such a transform (null propagation) is already being done somewhere. https://godbolt.org/g/ow79c8
I'd recommend to first look where that is happening, and extend that, not introduce a duplicate-but-better fold elsewhere.

But it does not work in basic case.. https://godbolt.org/g/wtimXj

In *another* basic case. It is clearly working in the case i linked, no?

In D45378#1060270, @xbolva00 wrote:

In D45378#1060239, @spatel wrote:

This is pushing instcombine beyond local simplifications. Propagating values across blocks should probably be handled in CVP (-correlated-propagation).

Take working example, save (slight manual cleaning required) it as test.ll

test.ll346 BDownload

,
and run $ opt -O2 -S test.ll -print-after-all (D44244 isn't there still),
and look for when line tail call void @bar(i8* %0) is replaced with tail call void @bar(i8* null)
That will tell you which pass does it currently. (spoiler: Global Value Numbering, hmm...)

Maybe, but here it also fits, every info required for this transformation is available here.

Implementation of this optimization would probably be quite massive in the CorrelatedValuePropagation.

But then you will have two similar folds doing essentially the same thing, but in different passes, and one is more broken than the other one.
So while this will may be easy to do right now, it is the wrong solution long-term, it will increase technical debt,
and someone later on will stumble into that and will have to either fix one of them, or deduplicate them...

[vivekvpandya]

I am not an expert for InstCombine. But I think @spatel has worked on it for long time so I think he is appropriate person to review this.

[spatel]

In D45378#1060270, @xbolva00 wrote:

In D45378#1060239, @spatel wrote:

This is pushing instcombine beyond local simplifications. Propagating values across blocks should probably be handled in CVP (-correlated-propagation).

Maybe, but here it also fits, every info required for this transformation is available here.

I think it's been shown that every other pass could be subsumed by instcombine. That doesn't mean we should do that.

Implementation of this optimization would probably be quite massive in the CorrelatedValuePropagation.

I was curious why that might be, so I wrote a patch. It's about the same amount of code as this patch, but more general. Please see if D45448 / rL329755 solved your motivating examples. If yes, I think you can abandon this patch.

[xbolva00]

In D45378#1064397, @spatel wrote:

In D45378#1060270, @xbolva00 wrote:

In D45378#1060239, @spatel wrote:

This is pushing instcombine beyond local simplifications. Propagating values across blocks should probably be handled in CVP (-correlated-propagation).

Maybe, but here it also fits, every info required for this transformation is available here.

I think it's been shown that every other pass could be subsumed by instcombine. That doesn't mean we should do that.

Implementation of this optimization would probably be quite massive in the CorrelatedValuePropagation.

I was curious why that might be, so I wrote a patch. It's about the same amount of code as this patch, but more general. Please see if D45448 / rL329755 solved your motivating examples. If yes, I think you can abandon this patch.

I checked clang trunk via godbolt and for https://godbolt.org/g/wtimXj (I didnt forget to switch to trunk) it is still same.

Edit: I checked godbolt again and now code looks well. Thanks!

lib/Transforms/InstCombine/InstructionCombining.cpp

2405

I think the current code is ok.

lib/Transforms/InstCombine/InstructionCombining.cpp

if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), TrueDest,
     // Swap destinations and condition.
     CmpInst *Cond = cast<CmpInst>(BI.getCondition());
     Cond->setPredicate(CmpInst::getInversePredicate(Pred));
     BI.swapSuccessors();
     Worklist.Add(Cond);
     return &BI;
   }
 
+  // Propagate null op from cmp to next basic blocks
+  if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Zero())), TrueDest,
+                      FalseDest)) &&
+      isCanonicalPredicate(Pred)) {
+    auto *Cmp = dyn_cast<CmpInst>(BI.getOperand(0));
+    Value *NullOp = Cmp->getOperand(0); // left side of cmp eq
+    bool NullOpPropagated = false;
+    BasicBlock *Next;
+    for (BasicBlock *B = TrueDest; B; B = Next) {
+      Next = nullptr;
+      for (Instruction &I : *B) {
+        for (unsigned i = 0; i < I.getNumOperands(); ++i) {
+          Value *Arg = I.getOperand(i);
+          if (match(Arg, m_Zero()) && NullOp->getType() == Arg->getType()) {
+            I.setOperand(i, NullOp);
+            NullOpPropagated |= true;
+          }
+        }
+
+        if (BranchInst *BI = dyn_cast<BranchInst>(&I)) {
+          if (BI->isUnconditional()) {
+            Next = dyn_cast<BasicBlock>(BI->getOperand(0));
+          }
+        }
+      }
+    }
+
+    if (NullOpPropagated)
+      return &BI;
+
     return nullptr;
 }
 
 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
   Value *Cond = SI.getCondition();
   Value *Op0;
   ConstantInt *AddRHS;
   if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) {
     // Change 'switch (X+4) case 1:' into 'switch (X) case -3'.

test/Transforms/InstCombine/cmp-propagate-zero-val.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+
+define i8* @propagate_null(i8* %ptr) #0 {
+; CHECK-LABEL: @propagate_null(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[PTR:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[PUTCHAR:%.*]] = call i32 @putchar(i32 10)
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i8* [[PTR]]
+;
+entry:
+  %retval = alloca i8*, align 4
+  %tobool = icmp ne i8* %ptr, null
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  store i8* null, i8** %retval, align 4
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call = call i32 @puts(i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i32 0, i32 0))
+  store i8* %ptr, i8** %retval, align 4
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %0 = load i8*, i8** %retval, align 4
+  ret i8* %0
+}
+
+declare i32 @puts(i8*) #1
+