[WIP] Minimal SCEV interval analysis

[jdoerfert]

Summary

This is a partly finished symbolic SCEV interval analysis that would
allow to bound parameters wrt. other parameters and not only
constants.

Thoughts are appreciated.

[Meinersbur]

Looks like this is trying to exploit information on llvm::Value's from instructions outside the SCoP. Nice idea and straightforward implementation.

As far as I can see this gets its range information from surrounding non-scop loops (AddRecExpr) and shared common instructions (SCEVUnknown). One could get more information from the LazyValueInfo pass.

Please add comments, it would make it easier to review the diff.

lib/Support/SCEVValidator.cpp

699

Know -> Known

755

visitCouldNotCompute missing?

[grosser]

Hi Johannes,

this is indeed a neat idea. The direction looks good. I suggest to move this out of the WIP state for us to be able to provide a full review.

[grosser]

This seems abonded. I drop this from my review list. Please add me back if this becomes active again.

include/polly/Support/SCEVValidator.h

 /// @brief Extract the constant factors from the multiplication @p M.
 ///
 /// @param M  A potential SCEV multiplication.
 /// @param SE The ScalarEvolution analysis to create new SCEVs.
 ///
 /// @returns The constant factor in @p M and the rest of @p M.
 std::pair<const llvm::SCEVConstant *, const llvm::SCEV *>
 extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE);
+
+struct SCEVInterval {
+  const llvm::SCEV *Min;
+  const llvm::SCEV *Max;
+  SCEVInterval() : Min(nullptr), Max(nullptr) {}
+  SCEVInterval(const llvm::SCEV *Min, const llvm::SCEV *Max)
+      : Min(Min), Max(Max) {}
+};
+
+SCEVInterval getInterval(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE);
 }
 
 #endif

lib/Analysis/ScopInfo.cpp

void Scop::buildContext() {
   AssumedContext = isl_set_universe(Space);
 }
 
 void Scop::addParameterBounds() {
   unsigned PDim = 0;
   for (auto *Parameter : Parameters) {
     ConstantRange SRange = SE->getSignedRange(Parameter);
     Context = addRangeBoundsToSet(Context, SRange, PDim++, isl_dim_param);
+
+    SCEVInterval SI = getInterval(Parameter, *SE);
+    if (SI.Min && SI.Min != Parameter &&
+        isAffineExpr(&getRegion(), nullptr, SI.Min, *SE)) {
+      auto *PPWA = getPwAffOnly(Parameter);
+      auto *MinPWA = getPwAffOnly(SI.Min);
+      auto *MinSet = isl_set_params(isl_pw_aff_ge_set(PPWA, MinPWA));
+      Context = isl_set_intersect(Context, MinSet);
+    }
+
+    if (SI.Max && SI.Max != Parameter &&
+        isAffineExpr(&getRegion(), nullptr, SI.Max, *SE)) {
+      auto *PPWA = getPwAffOnly(Parameter);
+      auto *MaxPWA = getPwAffOnly(SI.Max);
+      auto *MaxSet = isl_set_params(isl_pw_aff_le_set(PPWA, MaxPWA));
+      Context = isl_set_intersect(Context, MaxSet);
+    }
   }
 }
 
 void Scop::realignParams() {
   // Add all parameters into a common model.
   isl_space *Space = isl_space_params_alloc(getIslCtx(), ParameterIds.size());
 
   unsigned PDim = 0;

lib/Support/SCEVValidator.cpp

extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
   for (auto *Op : Mul->operands())
     if (isa<SCEVConstant>(Op))
       ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
     else
       LeftOver = SE.getMulExpr(LeftOver, Op);
 
   return std::make_pair(ConstPart, LeftOver);
 }
+
+/// @brief
+struct SCEVIntervalAnalysis
+    : public SCEVVisitor<SCEVIntervalAnalysis, SCEVInterval> {
+private:
+  ScalarEvolution &SE;
+
+public:
+  SCEVIntervalAnalysis(ScalarEvolution &SE) : SE(SE) {}
+
+  SCEVInterval visitConstant(const SCEVConstant *Constant) {
+    return SCEVInterval(Constant, Constant);
+  }
+
+  SCEVInterval visitTruncateExpr(const SCEVTruncateExpr *Expr) {
+    return SCEVInterval();
+  }
+
+  SCEVInterval visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+    return SCEVInterval();
+  }
+
+  SCEVInterval visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
+    return visit(Expr->getOperand());
+  }
+
+  SCEVInterval visitAddExpr(const SCEVAddExpr *Expr) {
+    return SCEVInterval();
+    // SCEVInterval Return = visit(Expr->getOperand(0));
+    // if (!Return.Min || !Return.Max)
+    // return SCEVInterval();
+
+    // for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
+    // SCEVInterval Op = visit(Expr->getOperand(i));
+    // if (!Op.Min || !Op.Max)
+    // return SCEVInterval();
+
+    // Return.Min = SE.getSMinExpr(Return.Min, Op.Min);
+    //}
+    // return Return;
+  }
+
+  SCEVInterval visitMulExpr(const SCEVMulExpr *Expr) { return SCEVInterval(); }
+
+  SCEVInterval visitUDivExpr(const SCEVUDivExpr *Expr) {
+    return SCEVInterval();
+  }
+
+  SCEVInterval visitAddRecExpr(const SCEVAddRecExpr *Expr) {
+    auto *StartSCEV = Expr->getStart();
+    auto *StepSCEV = Expr->getStepRecurrence(SE);
+    auto *TripCountSCEV = SE.getMaxBackedgeTakenCount(Expr->getLoop());
+    if (Expr->getType() == TripCountSCEV->getType()) {
+      /* No Op */
+    } else if (TripCountSCEV->getType()->getScalarSizeInBits() >
+               Expr->getType()->getScalarSizeInBits()) {
+      auto *Ty = TripCountSCEV->getType();
+      StartSCEV = SE.getSignExtendExpr(StartSCEV, Ty);
+      StepSCEV = SE.getSignExtendExpr(StepSCEV, Ty);
+    } else {
+      TripCountSCEV = SE.getSignExtendExpr(TripCountSCEV, Expr->getType());
+    }
+
+    SCEVInterval Start = visit(StartSCEV);
+    SCEVInterval Step = visit(StepSCEV);
+    bool IsKnowPos = SE.isKnownPositive(StepSCEV);
+    bool IsKnowNeg = !IsKnowPos && SE.isKnownNegative(StepSCEV);
+    if (!IsKnowPos && !IsKnowNeg)
+      return SCEVInterval();
+
+    auto *Min = IsKnowPos ? Start.Min : nullptr;
+    auto *Max = IsKnowNeg ? Start.Max : nullptr;
+    if (isa<SCEVCouldNotCompute>(TripCountSCEV))
+      return SCEVInterval(Min, Max);
+
+    SCEVInterval TripCount = visit(TripCountSCEV);
+    if (!TripCount.Max || !Step.Max)
+      return SCEVInterval(Min, Max);
+
+    auto *MaxOffset = SE.getMulExpr(TripCount.Max, Step.Max);
+    if ((IsKnowPos && !Start.Max) || (!IsKnowPos && !Start.Min))
+      return SCEVInterval(Min, Max);
+
+    if (IsKnowPos)
+      Max = SE.getAddExpr(Start.Max, MaxOffset);
+    else
+      Min = SE.getAddExpr(Start.Min, MaxOffset);
+
+    return SCEVInterval(Min, Max);
+  }
+
+  SCEVInterval visitSMaxExpr(const SCEVSMaxExpr *Expr) {
+    SCEVInterval Return = visit(Expr->getOperand(0));
+    if (!Return.Min || !Return.Max)
+      return SCEVInterval();
+
+    for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
+      SCEVInterval Op = visit(Expr->getOperand(i));
+      if (!Op.Min || !Op.Max)
+        return SCEVInterval();
+
+      Return.Min = SE.getSMaxExpr(Return.Min, Op.Min);
+      Return.Max = SE.getSMaxExpr(Return.Max, Op.Max);
+    }
+
+    return Return;
+  }
+
+  SCEVInterval visitUMaxExpr(const SCEVUMaxExpr *Expr) {
+    return SCEVInterval();
+  }
+
+  SCEVInterval visitUnknown(const SCEVUnknown *Expr) {
+    return SCEVInterval(Expr, Expr);
+  }
+};
+
+SCEVInterval getInterval(const SCEV *Expr, ScalarEvolution &SE) {
+  SCEVIntervalAnalysis SIA(SE);
+  return SIA.visit(Expr);
+}
 }