Fix a type mismatch assert in SCEV division

[bcahoon]

Summary

An assert was triggered when attempting to create a new SCEV with operands of different types in the visitAddRecExpr. In this test case, the operand types of the numerator and denominator are different. The SCEV division code should generate a conservative answer when this happens.

This patch depends on reviews.llvm.org/D9003.

[sanjoy]

How do we end up in a situation where the numerator and denominator have different types? I don't think dividing differently typed SCEV expressions should be a valid operation.

[bcahoon]

In the test case, the numerator ({0,+,(zext i16 %0 to i32)}<nw><%for.cond7.preheader>) is i32 and the denominator (%0) is i16. The second divide() call generates a value with type i32 for StepR (the remainder value for the Step). The types for the values returned by the first divide() call, StartQ and StartR, are both i16.

I think you're suggesting that the check for the type mismatch occur before the calls to divide() in visitAddRecExpr? That seems reasonable.

[sanjoy]

In D9021#156237, @bcahoon wrote:

In the test case, the numerator ({0,+,(zext i16 %0 to i32)}<nw><%for.cond7.preheader>) is i32 and the denominator (%0) is i16. The second divide() call generates a value with type i32 for StepR (the remainder value for the Step). The types for the values returned by the first divide() call, StartQ and StartR, are both i16.

I think you're suggesting that the check for the type mismatch occur before the calls to divide() in visitAddRecExpr? That seems reasonable.

I was initially suggesting that SCEV should not be attempting to divide integers of different bit-widths, and it should be up to the caller to sext or zext as needed. But visitConstant clearly tries to do something for differing bit-widths so that assumption was flawed. Therefore I think this change is okay as it is.

It might be helpful to explicitly document that SCEVDivision::divide sign extends the narrower integer to the width of the wider integer before division. Is it correct to state that invariant here is that if SCEVDivision::divide returns Q and R after dividing N by D then sext_if_needed(N) == sext_if_needed(Q) * sext_if_needed(D) + sext_if_needed(R) where sext_if_needed sign extends to the widest of widths of N and R? If so, it'll be helpful to document that too.

[bcahoon]

Hi Sanjoy - thanks for the review and comments. I appreciate the feedback.

In D9021#156823, @sanjoy wrote:

It might be helpful to explicitly document that SCEVDivision::divide sign extends the narrower integer to the width of the wider integer before division. Is it correct to state that invariant here is that if SCEVDivision::divide returns Q and R after dividing N by D then sext_if_needed(N) == sext_if_needed(Q) * sext_if_needed(D) + sext_if_needed(R) where sext_if_needed sign extends to the widest of widths of N and R? If so, it'll be helpful to document that too.

I'm also curious if the the invariant you state above is true in all cases. Clearly, it is assumed in some cases, for example, in visitConstant, as you mention. If so, it should be possible to explicitly sign extend when needed, and then remove the various checks for a type mismatch in the visitor functions. This could help generate more precise results.

lib/Analysis/ScalarEvolution.cpp

void visitConstant(const SCEVConstant *Numerator) {
     }
   }
 
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
     const SCEV *StartQ, *StartR, *StepQ, *StepR;
     assert(Numerator->isAffine() && "Numerator should be affine");
     divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
     divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
+    // Bail out if types do not match.
+    Type *Ty = Denominator->getType();
+    if (Ty != StartQ->getType() || Ty != StartR->getType() ||
+        Ty != StepQ->getType() || Ty != StepR->getType()) {
+      Quotient = Zero;
+      Remainder = Numerator;
+      return;
+    }
     Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
                                 Numerator->getNoWrapFlags());
     Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
                                  Numerator->getNoWrapFlags());
   }
 
   void visitAddExpr(const SCEVAddExpr *Numerator) {
     SmallVector<const SCEV *, 2> Qs, Rs;

test/Analysis/Delinearization/type_mismatch.ll

+; RUN: opt < %s -analyze -delinearize
+; REQUIRES: asserts
+
+; Test that SCEV divide code doesn't crash when attempting to create a SCEV
+; with operands of different types. In this case, the visitAddRecExpr
+; function tries to create an AddRec where the start and step are different
+; types.
+
+target datalayout = "e-m:e-p:32:32-i64:64-a:0-v32:32-n16:32"
+
+define fastcc void @test() {
+entry:
+  %0 = load i16, i16* undef, align 2
+  %conv21 = zext i16 %0 to i32
+  br label %for.cond7.preheader
+
+for.cond7.preheader:
+  %p1.022 = phi i8* [ undef, %entry ], [ %add.ptr, %for.end ]
+  br label %for.body11
+
+for.body11:
+  %arrayidx.phi = phi i8* [ %p1.022, %for.cond7.preheader ], [ undef, %for.body11 ]
+  store i8 undef, i8* %arrayidx.phi, align 1
+  br i1 undef, label %for.body11, label %for.end
+
+for.end:
+  %add.ptr = getelementptr inbounds i8, i8* %p1.022, i32 %conv21
+  br label %for.cond7.preheader
+}