Don't reorder multiplies in extractConstantFactor

[efriedma]

Summary

The existing code would add the operands in the wrong order, and eventually crash because the SCEV expression doesn't exactly match the parameter SCEV expression in SCEVAffinator::visit. (SCEV doesn't sort the operands to getMulExpr in general.)

[grosser]

Hi Eli,

thank you for catching this. The patch looks good, just two minor comments below.

Best,
Tobias

test/ScopInfo/scop-affine-parameter-ordering.ll

1 ↗

(On Diff #68282)

You could drop -polly-code-generator=isl here. It should not affect (or be needed) for this test case.

7 ↗

(On Diff #68282)

To make sure we do not loose test coverage over time, it might be good to use '-analyze' and to also check that we construct the right scop.

; CHECK: Stmt_for_body8_us_us95_i
; CHECK-NEXT: Domain :=
; CHECK-NEXT: [p_0] -> { Stmt_for_body8_us_us95_i[i0] : 0 <= i0 <= 4 };
; CHECK-NEXT: Schedule :=
; CHECK-NEXT: [p_0] -> { Stmt_for_body8_us_us95_i[i0] -> [i0] };
; CHECK-NEXT; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
; CHECK-NEXT; [p_0] -> { Stmt_for_body8_us_us95_i[i0] -> MemRef_0[1 + p_0] };
; CHECK-NEXT }

polly/trunk/lib/Support/SCEVValidator.cpp

ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
   ValidatorResult Result = Validator.visit(Expr);
   assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
 
   return Result.getParameters();
 }
 
 std::pair<const SCEVConstant *, const SCEV *>
 extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
-
-  auto *LeftOver = SE.getConstant(S->getType(), 1);
   auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
 
   if (auto *Constant = dyn_cast<SCEVConstant>(S))
-    return std::make_pair(Constant, LeftOver);
+    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
 
   auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
   if (AddRec) {
     auto *StartExpr = AddRec->getStart();
     if (StartExpr->isZero()) {
       auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
       auto *LeftOverAddRec =
           SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
if (auto *Add = dyn_cast<SCEVAddExpr>(S)) {
     auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
     return std::make_pair(Factor, NewAdd);
   }
 
   auto *Mul = dyn_cast<SCEVMulExpr>(S);
   if (!Mul)
     return std::make_pair(ConstPart, S);
 
+  SmallVector<const SCEV *, 4> LeftOvers;
   for (auto *Op : Mul->operands())
     if (isa<SCEVConstant>(Op))
       ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
     else
-      LeftOver = SE.getMulExpr(LeftOver, Op);
+      LeftOvers.push_back(Op);
 
-  return std::make_pair(ConstPart, LeftOver);
+  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
 }
 } // namespace polly

polly/trunk/test/ScopInfo/scop-affine-parameter-ordering.ll

+; RUN: opt -polly-process-unprofitable -polly-scops %s -analyze | FileCheck %s
+target datalayout = "e-m:e-i64:64-i128:128-n8:16:32:64-S128"
+target triple = "aarch64--linux-android"
+
+; Check for SCOP:
+; CHECK: Stmt_for_body8_us_us95_i
+; CHECK-NEXT: Domain :=
+; CHECK-NEXT: [p_0] -> { Stmt_for_body8_us_us95_i[i0] : 0 <= i0 <= 4 };
+; CHECK-NEXT: Schedule :=
+; CHECK-NEXT: [p_0] -> { Stmt_for_body8_us_us95_i[i0] -> [i0] };
+; CHECK-NEXT; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT; [p_0] -> { Stmt_for_body8_us_us95_i[i0] -> MemRef_0[1 + p_0] };
+; CHECK-NEXT }
+
+define void @test1() unnamed_addr align 2 {
+entry:
+  %xFactor.0.reload = load i32, i32* undef
+  %0 = load i8*, i8** undef, align 8
+  %div = udiv i32 0, %xFactor.0.reload
+  %1 = load i32, i32* undef, align 4
+  %mul = mul i32 %1, %xFactor.0.reload
+  %col.023.us.us85.i = add i32 %div, -1
+  %mul11.us.us93.i = mul i32 %col.023.us.us85.i, %mul
+  br label %for.body8.us.us95.i
+
+for.body8.us.us95.i:
+  %niter.i = phi i32 [ %niter.i.next, %for.body8.us.us95.i ], [ 0, %entry ]
+  %add12.us.us100.1.i = add i32 1, %mul11.us.us93.i
+  %idxprom13.us.us101.1.i = zext i32 %add12.us.us100.1.i to i64
+  %arrayidx14.us.us102.1.i = getelementptr inbounds i8, i8* %0, i64 %idxprom13.us.us101.1.i
+  store i8 0, i8* %arrayidx14.us.us102.1.i, align 1
+  %niter.ncmp.3.i = icmp eq i32 %niter.i, 4
+  %niter.i.next = add i32 %niter.i, 1
+  br i1 %niter.ncmp.3.i, label %for.body8.us.us95.epil.i.preheader, label %for.body8.us.us95.i
+
+for.body8.us.us95.epil.i.preheader:
+  ret void
+}
+