Allow signed division in access functions

[jdoerfert]

commited in r228833.

lib/Analysis/ScopInfo.cpp

private:
   __isl_give isl_pw_aff *visitSignExtendExpr(const SCEVSignExtendExpr *Expr);
   __isl_give isl_pw_aff *visitAddExpr(const SCEVAddExpr *Expr);
   __isl_give isl_pw_aff *visitMulExpr(const SCEVMulExpr *Expr);
   __isl_give isl_pw_aff *visitUDivExpr(const SCEVUDivExpr *Expr);
   __isl_give isl_pw_aff *visitAddRecExpr(const SCEVAddRecExpr *Expr);
   __isl_give isl_pw_aff *visitSMaxExpr(const SCEVSMaxExpr *Expr);
   __isl_give isl_pw_aff *visitUMaxExpr(const SCEVUMaxExpr *Expr);
   __isl_give isl_pw_aff *visitUnknown(const SCEVUnknown *Expr);
+  __isl_give isl_pw_aff *visitSDivInstruction(Instruction *SDiv);
 
   friend struct SCEVVisitor<SCEVAffinator, isl_pw_aff *>;
 };
 
 SCEVAffinator::SCEVAffinator(const ScopStmt *Stmt)
     : Ctx(Stmt->getIslCtx()), NbLoopSpaces(Stmt->getNumIterators()),
       S(Stmt->getParent()) {}
 
__isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
 
   return Max;
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
   llvm_unreachable("SCEVUMaxExpr not yet supported");
 }
 
+__isl_give isl_pw_aff *SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {
+  assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!");
+  auto *SE = S->getSE();
+
+  auto *Divisor = SDiv->getOperand(1);
+  auto *DivisorSCEV = SE->getSCEV(Divisor);
+  auto *DivisorPWA = visit(DivisorSCEV);
+  assert(isa<ConstantInt>(Divisor) &&
+         "SDiv is no parameter but has a non-constant RHS.");
+
+  auto *Dividend = SDiv->getOperand(0);
+  auto *DividendSCEV = SE->getSCEV(Dividend);
+  auto *DividendPWA = visit(DividendSCEV);
+  return isl_pw_aff_tdiv_q(DividendPWA, DivisorPWA);
+}
+
 __isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
-  llvm_unreachable("Unknowns are always parameters");
+  if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
+    switch (I->getOpcode()) {
+    case Instruction::SDiv:
+      return visitSDivInstruction(I);
+    default:
+      break; // Fall through.
+    }
+  }
+
+  llvm_unreachable(
+      "Unknowns SCEV was neither parameter nor a valid instruction.");
 }
 
 int SCEVAffinator::getLoopDepth(const Loop *L) {
   Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
   assert(outerLoop && "Scop does not contain this loop");
   return L->getLoopDepth() - outerLoop->getLoopDepth();
 }
 

lib/Support/SCEVValidator.cpp

for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
         DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
         return ValidatorResult(SCEVType::INVALID);
       }
     }
 
     return ValidatorResult(SCEVType::PARAM, Expr);
   }
 
+  ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
+    if (R->contains(I)) {
+      DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
+                      "within the region\n");
+      return ValidatorResult(SCEVType::INVALID);
+    }
+
+    return ValidatorResult(SCEVType::PARAM, S);
+  }
+
+  ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *S) {
+    assert(SDiv->getOpcode() == Instruction::SDiv &&
+           "Assumed SDiv instruction!");
+
+    auto *Divisor = SDiv->getOperand(1);
+    auto *CI = dyn_cast<ConstantInt>(Divisor);
+    if (!CI)
+      return visitGenericInst(SDiv, S);
+
+    auto *Dividend = SDiv->getOperand(0);
+    auto *DividendSCEV = SE.getSCEV(Dividend);
+    return visit(DividendSCEV);
+  }
+
   ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
     Value *V = Expr->getValue();
 
     if (!(Expr->getType()->isIntegerTy() || Expr->getType()->isPointerTy())) {
       DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer type");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     if (isa<UndefValue>(V)) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
       return ValidatorResult(SCEVType::INVALID);
     }
 
-    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
-      if (R->contains(I)) {
-        DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
-                        "within the region\n");
-        return ValidatorResult(SCEVType::INVALID);
-      }
-
     if (BaseAddress == V) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references BaseAddress\n");
       return ValidatorResult(SCEVType::INVALID);
     }
 
+    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
+      switch (I->getOpcode()) {
+      case Instruction::SDiv:
+        return visitSDivInstruction(I, Expr);
+      default:
+        return visitGenericInst(I, Expr);
+      }
+    }
+
     return ValidatorResult(SCEVType::PARAM, Expr);
   }
 };
 
 /// @brief Check whether a SCEV refers to an SSA name defined inside a region.
 ///
 struct SCEVInRegionDependences
     : public SCEVVisitor<SCEVInRegionDependences, bool> {

test/ScopInfo/NonAffine/non_affine_but_sdiv.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:   [N] -> { Stmt_for_body[i0] -> MemRef_A[o0] : (N >= 0 and 5o0 >= -4 + N + 5i0 and 5o0 <= N + 5i0) or (N <= -1 and 5o0 >= N + 5i0 and 5o0 <= 4 + N + 5i0) };
+; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:   [N] -> { Stmt_for_body[i0] -> MemRef_A[o0] : (N <= 0 and 5o0 <= -N + 5i0 and 5o0 >= -4 - N + 5i0) or (N >= 1 and 5o0 <= 4 - N + 5i0 and 5o0 >= -N + 5i0) };
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++)
+;        A[i] = A[i + (N / 5)] + A[i + (N / -5)];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %div = sdiv i32 %N, 5
+  %tmp1 = trunc i64 %indvars.iv to i32
+  %add = add nsw i32 %tmp1, %div
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
+  %tmp2 = load i32* %arrayidx, align 4
+  %div1 = sdiv i32 %N, -5
+  %tmp3 = trunc i64 %indvars.iv to i32
+  %add2 = add nsw i32 %tmp3, %div1
+  %idxprom3 = sext i32 %add2 to i64
+  %arrayidx4 = getelementptr inbounds i32* %A, i64 %idxprom3
+  %tmp4 = load i32* %arrayidx4, align 4
+  %add5 = add nsw i32 %tmp2, %tmp4
+  %arrayidx7 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %add5, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}