[ValueTracking] Teach computeKnownBits for PHI nodes to compute sign bit for a recurrence with a NSW addition.

[craig.topper]

Summary

If a operation for a recurrence is an addition with no signed wrap and both input sign bits are 0, then the result sign bit must also be 0. Similar for the negative case.

I found this deficiency while playing around with a loop in the x86 backend that contained a signed division that could be optimized into an unsigned division if we could prove both inputs were positive. One of them being the loop induction variable. With this patch we can perform the conversion for this case. The test case here is a contrived variation of the loop I was looking at.

[sanjoy]

lib/Analysis/ValueTracking.cpp

1251 ↗

(On Diff #61171)

Can you please add a test for this second bit (i.e. negative stays negative)?

[craig.topper]

lib/Analysis/ValueTracking.cpp

1251 ↗

(On Diff #61171)

Do you have a suggestion for how to test that? I knew of the sign bit being 0 check in instcombine of sdiv so I used that for the 0 case. But I don't know enough about what optimizations can benefit from knowing the sign bit is set.

[sanjoy]

lib/Analysis/ValueTracking.cpp

1251 ↗

(On Diff #61171)

Perhaps you could check that a bitwise-and with 1 << (bitwidth - 1) folds to a constant? If that doesn't fold despite knowing the sign bit, then that's a separate bug. :)

[craig.topper]

I've added the additional test case for negative staying negative.

[sanjoy]

lgtm (with text so that it goes to the list this time)

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (P->getNumIncomingValues() == 2) {
 
           // We need to take the minimum number of known bits
           APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
           computeKnownBits(L, KnownZero3, KnownOne3, Depth + 1, Q);
 
           KnownZero = APInt::getLowBitsSet(BitWidth,
                                            std::min(KnownZero2.countTrailingOnes(),
                                                     KnownZero3.countTrailingOnes()));
+
+          // If the operation is an addition that can't have signed overflow,
+          // then the sign bit is known to be zero if both input sign bits
+          // are zero. Similar for two negative inputs.
+          if (Opcode == Instruction::Add &&
+              cast<OverflowingBinaryOperator>(LU)->hasNoSignedWrap()) {
+            if (KnownZero2.isNegative() && KnownZero3.isNegative())
+              KnownZero.setBit(BitWidth-1);
+            if (KnownOne2.isNegative() && KnownOne3.isNegative())
+              KnownOne.setBit(BitWidth-1);
+          }
+
           break;
         }
       }
     }
 
     // Unreachable blocks may have zero-operand PHI nodes.
     if (P->getNumIncomingValues() == 0)
       break;

llvm/trunk/test/Transforms/BBVectorize/loop1.ll

 ; CHECK-UNRL: %add7 = fadd <2 x double> %add, %mul6
 ; CHECK-UNRL: %mul8 = fmul <2 x double> %3, %3
 ; CHECK-UNRL: %add9 = fadd <2 x double> %2, %2
 ; CHECK-UNRL: %add10 = fadd <2 x double> %add9, %2
 ; CHECK-UNRL: %mul11 = fmul <2 x double> %mul8, %add10
 ; CHECK-UNRL: %add12 = fadd <2 x double> %add7, %mul11
 ; CHECK-UNRL: %4 = bitcast double* %arrayidx14 to <2 x double>*
 ; CHECK-UNRL: store <2 x double> %add12, <2 x double>* %4, align 8
-; CHECK-UNRL: %indvars.iv.next.1 = add nsw i64 %indvars.iv, 2
+; CHECK-UNRL: %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
 ; CHECK-UNRL: %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32
 ; CHECK-UNRL: %exitcond.1 = icmp eq i32 %lftr.wideiv.1, 10
 ; CHECK-UNRL: br i1 %exitcond.1, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

llvm/trunk/test/Transforms/InstCombine/phi.ll

if.else:                                          ; preds = %entry
   %1 = select i1 %cmp, i32 1, i32 2
   br label %if.end
 
 if.end:                                           ; preds = %entry, %if.then
   %a.0 = phi i32 [ %1,  %if.else], [ %n, %entry ], [2, %if.then]
   %cmp1 = icmp ne i32 %a.0, 0
   ret i1  %cmp1
 }
+
+
+; This test makes sure we can determine that the inputs to the sdiv in the loop
+; are non-negative and can become a udiv. This requires that we recognize that
+; the loop induction can never have its sign bit set.
+;
+; CHECK-LABEL: @phi_nsw_induction_sdiv_udiv
+; CHECK: udiv
+; CHECK: udiv
+define i32 @phi_nsw_induction_sdiv_udiv(i32 %NumElts, i32 %ScalarSize) {
+entry:
+  %div = udiv i32 128, %ScalarSize
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %Sum.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ne i32 %i.0, %NumElts
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  ; this should become a udiv
+  %div1 = sdiv i32 %i.0, %div
+  %add = add nsw i32 %Sum.0, %div1
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %Sum.0
+}
+
+
+; CHECK-LABEL: test_positive_nsw_recurrence
+; CHECK-NOT: bar
+; CHECK: foo
+; CHECK-NOT: bar
+; CHECK: ret
+define void @test_positive_nsw_recurrence(i32 %N) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ne i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %and = and i32 %i.0, -2147483648
+  %tobool = icmp ne i32 %and, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  ; this call should be deleted as %i.0 can never be negative due to no signed wrap
+  call void @bar()
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  call void @foo()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+; CHECK-LABEL: test_negative_nsw_recurrence
+; CHECK-NOT: foo
+; CHECK: bar
+; CHECK-NOT: foo
+; CHECK: ret
+define void @test_negative_nsw_recurrence(i32 %N) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ -1, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ne i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %and = and i32 %i.0, -2147483648
+  %tobool = icmp ne i32 %and, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  call void @bar()
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  ; this call should be deleted as %i.0 can never be positive due to no signed wrap
+  call void @foo()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc = add nsw i32 %i.0, -1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @bar()
+declare void @foo()