SCEVValidator: Move into own file

llvm-svn: 143960

4 files changed, 264 insertions, 226 deletions

diff --git a/polly/include/polly/Support/SCEVValidator.h b/polly/include/polly/Support/SCEVValidator.h
new file mode 100755
index 00000000000..d4d0b2ac921
--- /dev/null
+++ b/polly/include/polly/Support/SCEVValidator.h
@@ -0,0 +1,27 @@
+//===--- SCEVValidator.h - Detect Scops -------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Checks if a SCEV expression represents a valid affine expression.
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SCEV_VALIDATOR_H
+#define POLLY_SCEV_VALIDATOR_H
+
+namespace llvm {
+  class Region;
+  class SCEV;
+  class ScalarEvolution;
+  class Value;
+}
+
+namespace polly {
+  bool isAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
+                    llvm::ScalarEvolution &SE, llvm::Value **BaseAddress = 0);
+}
+
+#endif
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 883fe2ceafc..efc7dfa3f85 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -48,6 +48,7 @@
 
 #include "polly/LinkAllPasses.h"
 #include "polly/Support/ScopHelper.h"
+#include "polly/Support/SCEVValidator.h"
 #include "polly/Support/AffineSCEVIterator.h"
 
 #include "llvm/LLVMContext.h"
@@ -108,227 +109,6 @@ BADSCOP_STAT(Other,           "Others");
 
 //===----------------------------------------------------------------------===//
 // ScopDetection.
-
-namespace SCEVType {
-  enum TYPE {INT, PARAM, IV, INVALID};
-}
-
-struct ValidatorResult {
-  SCEVType::TYPE type;
-
-  ValidatorResult() : type(SCEVType::INVALID) {};
-
-  ValidatorResult(const ValidatorResult &vres) {
-    type = vres.type;
-  };
-
-  ValidatorResult(SCEVType::TYPE type) : type(type) {};
-
-  bool isConstant() {
-    return type == SCEVType::INT || type == SCEVType::PARAM;
-  }
-
-  bool isValid() {
-    return type != SCEVType::INVALID;
-  }
-
-  bool isIV() {
-    return type == SCEVType::IV;
-  }
-
-  bool isINT() {
-    return type == SCEVType::INT;
-  }
-};
-
-/// Check if a SCEV is valid in a SCoP.
-struct SCEVValidator
-  : public SCEVVisitor<SCEVValidator, struct ValidatorResult> {
-private:
-  const Region *R;
-  ScalarEvolution &SE;
-  Value **BaseAddress;
-
-public:
-  static bool isValid(const Region *R, const SCEV *Scev,
-                      ScalarEvolution &SE,
-                      Value **BaseAddress = NULL) {
-    if (isa<SCEVCouldNotCompute>(Scev))
-      return false;
-
-    if (BaseAddress)
-      *BaseAddress = NULL;
-
-    SCEVValidator Validator(R, SE, BaseAddress);
-    ValidatorResult Result = Validator.visit(Scev);
-
-    return Result.isValid();
-  }
-
-  SCEVValidator(const Region *R, ScalarEvolution &SE,
-                Value **BaseAddress) : R(R), SE(SE),
-    BaseAddress(BaseAddress) {};
-
-  struct ValidatorResult visitConstant(const SCEVConstant *Constant) {
-    return ValidatorResult(SCEVType::INT);
-  }
-
-  struct ValidatorResult visitTruncateExpr(const SCEVTruncateExpr* Expr) {
-    ValidatorResult Op = visit(Expr->getOperand());
-
-    // We currently do not represent a truncate expression as an affine
-    // expression. If it is constant during Scop execution, we treat it as a
-    // parameter, otherwise we bail out.
-    if (Op.isConstant())
-      return ValidatorResult(SCEVType::PARAM);
-
-    return ValidatorResult (SCEVType::INVALID);
-  }
-
-  struct ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr * Expr) {
-    ValidatorResult Op = visit(Expr->getOperand());
-
-    // We currently do not represent a zero extend expression as an affine
-    // expression. If it is constant during Scop execution, we treat it as a
-    // parameter, otherwise we bail out.
-    if (Op.isConstant())
-      return ValidatorResult (SCEVType::PARAM);
-
-    return ValidatorResult(SCEVType::INVALID);
-  }
-
-  struct ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr* Expr) {
-    // We currently allow only signed SCEV expressions. In the case of a
-    // signed value, a sign extend is a noop.
-    //
-    // TODO: Reconsider this when we add support for unsigned values.
-    return visit(Expr->getOperand());
-  }
-
-  struct ValidatorResult visitAddExpr(const SCEVAddExpr* Expr) {
-    ValidatorResult Return(SCEVType::INT);
-
-    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
-      ValidatorResult Op = visit(Expr->getOperand(i));
-
-      if (!Op.isValid())
-        return ValidatorResult(SCEVType::INVALID);
-
-      Return.type = std::max(Return.type, Op.type);
-    }
-
-    // TODO: Check for NSW and NUW.
-    return Return;
-  }
-
-  struct ValidatorResult visitMulExpr(const SCEVMulExpr* Expr) {
-    ValidatorResult Return(SCEVType::INT);
-
-    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
-      ValidatorResult Op = visit(Expr->getOperand(i));
-
-      if (Op.type == SCEVType::INT)
-        continue;
-
-      if (Op.type == SCEVType::INVALID || Return.type != SCEVType::INT)
-        return ValidatorResult(SCEVType::INVALID);
-
-      Return.type = Op.type;
-    }
-
-    // TODO: Check for NSW and NUW.
-    return Return;
-  }
-
-  struct ValidatorResult visitUDivExpr(const SCEVUDivExpr* Expr) {
-    ValidatorResult LHS = visit(Expr->getLHS());
-    ValidatorResult RHS = visit(Expr->getRHS());
-
-    // We currently do not represent a unsigned devision as an affine
-    // expression. If the division is constant during Scop execution we treat it
-    // as a parameter, otherwise we bail out.
-    if (LHS.isConstant() && RHS.isConstant())
-      return ValidatorResult(SCEVType::PARAM);
-
-    return ValidatorResult(SCEVType::INVALID);
-  }
-
-  struct ValidatorResult visitAddRecExpr(const SCEVAddRecExpr* Expr) {
-    if (!Expr->isAffine())
-      return ValidatorResult(SCEVType::INVALID);
-
-    ValidatorResult Start = visit(Expr->getStart());
-    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
-
-    if (!Start.isValid() || !Recurrence.isValid() || Recurrence.isIV())
-      return ValidatorResult(SCEVType::INVALID);
-
-
-    if (!R->contains(Expr->getLoop())) {
-      if (Start.isIV())
-        return ValidatorResult(SCEVType::INVALID);
-      else
-        return ValidatorResult(SCEVType::PARAM);
-    }
-
-    if (!Recurrence.isINT())
-      return ValidatorResult(SCEVType::INVALID);
-
-    return ValidatorResult(SCEVType::IV);
-  }
-
-  struct ValidatorResult visitSMaxExpr(const SCEVSMaxExpr* Expr) {
-    ValidatorResult Return(SCEVType::INT);
-
-    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
-      ValidatorResult Op = visit(Expr->getOperand(i));
-
-      if (!Op.isValid())
-        return ValidatorResult(SCEVType::INVALID);
-
-      Return.type = std::max(Return.type, Op.type);
-    }
-
-    return Return;
-  }
-
-  struct ValidatorResult visitUMaxExpr(const SCEVUMaxExpr* Expr) {
-    // We do not support unsigned operations. If 'Expr' is constant during Scop
-    // execution we treat this as a parameter, otherwise we bail out.
-    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
-      ValidatorResult Op = visit(Expr->getOperand(i));
-
-      if (!Op.isConstant())
-        return ValidatorResult(SCEVType::INVALID);
-    }
-
-    return ValidatorResult(SCEVType::PARAM);
-  }
-
-  ValidatorResult visitUnknown(const SCEVUnknown* Expr) {
-    Value *V = Expr->getValue();
-
-    if (isa<UndefValue>(V))
-      return ValidatorResult(SCEVType::INVALID);
-
-    if (BaseAddress) {
-      if (*BaseAddress)
-        return ValidatorResult(SCEVType::INVALID);
-      else
-        *BaseAddress = V;
-    }
-
-    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
-      if (R->contains(I))
-        return ValidatorResult(SCEVType::INVALID);
-
-    if (BaseAddress)
-      return ValidatorResult(SCEVType::PARAM);
-    else
-      return ValidatorResult(SCEVType::PARAM);
-  }
-};
-
 bool ScopDetection::isMaxRegionInScop(const Region &R) const {
   // The Region is valid only if it could be found in the set.
   return ValidRegions.count(&R);
@@ -457,8 +237,8 @@ bool ScopDetection::isValidCFG(BasicBlock &BB, DetectionContext &Context) const
     const SCEV *ScevLHS = SE->getSCEV(ICmp->getOperand(0));
     const SCEV *ScevRHS = SE->getSCEV(ICmp->getOperand(1));
 
-    bool affineLHS = SCEVValidator::isValid(&Context.CurRegion, ScevLHS, *SE);
-    bool affineRHS = SCEVValidator::isValid(&Context.CurRegion, ScevRHS, *SE);
+    bool affineLHS = isAffineExpr(&Context.CurRegion, ScevLHS, *SE);
+    bool affineRHS = isAffineExpr(&Context.CurRegion, ScevRHS, *SE);
 
     if (!affineLHS || !affineRHS)
       INVALID(AffFunc, "Non affine branch in BB: " + BB.getNameStr());
@@ -499,8 +279,7 @@ bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
   Value *Ptr = getPointerOperand(Inst), *BasePtr;
   const SCEV *AccessFunction = SE->getSCEV(Ptr);
 
-  if (!SCEVValidator::isValid(&Context.CurRegion, AccessFunction, *SE,
-                                 &BasePtr))
+  if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, &BasePtr))
     INVALID(AffFunc, "Bad memory address " << *AccessFunction);
 
   // FIXME: Also check with isValidAffineFunction, as for the moment it is
@@ -628,7 +407,7 @@ bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
 
   // Is the loop count affine?
   const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
-  if (!SCEVValidator::isValid(&Context.CurRegion, LoopCount, *SE))
+  if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE))
     INVALID(LoopBound, "Non affine loop bound '" << *LoopCount << "' in loop: "
                        << L->getHeader()->getNameStr());
 
diff --git a/polly/lib/Support/CMakeLists.txt b/polly/lib/Support/CMakeLists.txt
index a869e5cb532..86e21efd5ec 100755
--- a/polly/lib/Support/CMakeLists.txt
+++ b/polly/lib/Support/CMakeLists.txt
@@ -1,5 +1,6 @@
 add_polly_library(PollySupport
   AffSCEVItTester.cpp
   GICHelper.cpp
+  SCEVValidator.cpp
   ScopHelper.cpp
   )
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
new file mode 100644
index 00000000000..52de6bc087c
--- /dev/null
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -0,0 +1,231 @@
+
+#include "polly/Support/SCEVValidator.h"
+
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/RegionInfo.h"
+
+using namespace llvm;
+
+namespace SCEVType {
+  enum TYPE {INT, PARAM, IV, INVALID};
+}
+
+struct ValidatorResult {
+  SCEVType::TYPE type;
+
+  ValidatorResult() : type(SCEVType::INVALID) {};
+
+  ValidatorResult(const ValidatorResult &vres) {
+    type = vres.type;
+  };
+
+  ValidatorResult(SCEVType::TYPE type) : type(type) {};
+
+  bool isConstant() {
+    return type == SCEVType::INT || type == SCEVType::PARAM;
+  }
+
+  bool isValid() {
+    return type != SCEVType::INVALID;
+  }
+
+  bool isIV() {
+    return type == SCEVType::IV;
+  }
+
+  bool isINT() {
+    return type == SCEVType::INT;
+  }
+};
+
+/// Check if a SCEV is valid in a SCoP.
+struct SCEVValidator
+  : public SCEVVisitor<SCEVValidator, struct ValidatorResult> {
+private:
+  const Region *R;
+  ScalarEvolution &SE;
+  Value **BaseAddress;
+
+public:
+  SCEVValidator(const Region *R, ScalarEvolution &SE,
+                Value **BaseAddress) : R(R), SE(SE),
+    BaseAddress(BaseAddress) {};
+
+  struct ValidatorResult visitConstant(const SCEVConstant *Constant) {
+    return ValidatorResult(SCEVType::INT);
+  }
+
+  struct ValidatorResult visitTruncateExpr(const SCEVTruncateExpr* Expr) {
+    ValidatorResult Op = visit(Expr->getOperand());
+
+    // We currently do not represent a truncate expression as an affine
+    // expression. If it is constant during Scop execution, we treat it as a
+    // parameter, otherwise we bail out.
+    if (Op.isConstant())
+      return ValidatorResult(SCEVType::PARAM);
+
+    return ValidatorResult (SCEVType::INVALID);
+  }
+
+  struct ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr * Expr) {
+    ValidatorResult Op = visit(Expr->getOperand());
+
+    // We currently do not represent a zero extend expression as an affine
+    // expression. If it is constant during Scop execution, we treat it as a
+    // parameter, otherwise we bail out.
+    if (Op.isConstant())
+      return ValidatorResult (SCEVType::PARAM);
+
+    return ValidatorResult(SCEVType::INVALID);
+  }
+
+  struct ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr* Expr) {
+    // We currently allow only signed SCEV expressions. In the case of a
+    // signed value, a sign extend is a noop.
+    //
+    // TODO: Reconsider this when we add support for unsigned values.
+    return visit(Expr->getOperand());
+  }
+
+  struct ValidatorResult visitAddExpr(const SCEVAddExpr* Expr) {
+    ValidatorResult Return(SCEVType::INT);
+
+    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
+      ValidatorResult Op = visit(Expr->getOperand(i));
+
+      if (!Op.isValid())
+        return ValidatorResult(SCEVType::INVALID);
+
+      Return.type = std::max(Return.type, Op.type);
+    }
+
+    // TODO: Check for NSW and NUW.
+    return Return;
+  }
+
+  struct ValidatorResult visitMulExpr(const SCEVMulExpr* Expr) {
+    ValidatorResult Return(SCEVType::INT);
+
+    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
+      ValidatorResult Op = visit(Expr->getOperand(i));
+
+      if (Op.type == SCEVType::INT)
+        continue;
+
+      if (Op.type == SCEVType::INVALID || Return.type != SCEVType::INT)
+        return ValidatorResult(SCEVType::INVALID);
+
+      Return.type = Op.type;
+    }
+
+    // TODO: Check for NSW and NUW.
+    return Return;
+  }
+
+  struct ValidatorResult visitUDivExpr(const SCEVUDivExpr* Expr) {
+    ValidatorResult LHS = visit(Expr->getLHS());
+    ValidatorResult RHS = visit(Expr->getRHS());
+
+    // We currently do not represent a unsigned devision as an affine
+    // expression. If the division is constant during Scop execution we treat it
+    // as a parameter, otherwise we bail out.
+    if (LHS.isConstant() && RHS.isConstant())
+      return ValidatorResult(SCEVType::PARAM);
+
+    return ValidatorResult(SCEVType::INVALID);
+  }
+
+  struct ValidatorResult visitAddRecExpr(const SCEVAddRecExpr* Expr) {
+    if (!Expr->isAffine())
+      return ValidatorResult(SCEVType::INVALID);
+
+    ValidatorResult Start = visit(Expr->getStart());
+    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
+
+    if (!Start.isValid() || !Recurrence.isValid() || Recurrence.isIV())
+      return ValidatorResult(SCEVType::INVALID);
+
+
+    if (!R->contains(Expr->getLoop())) {
+      if (Start.isIV())
+        return ValidatorResult(SCEVType::INVALID);
+      else
+        return ValidatorResult(SCEVType::PARAM);
+    }
+
+    if (!Recurrence.isINT())
+      return ValidatorResult(SCEVType::INVALID);
+
+    return ValidatorResult(SCEVType::IV);
+  }
+
+  struct ValidatorResult visitSMaxExpr(const SCEVSMaxExpr* Expr) {
+    ValidatorResult Return(SCEVType::INT);
+
+    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
+      ValidatorResult Op = visit(Expr->getOperand(i));
+
+      if (!Op.isValid())
+        return ValidatorResult(SCEVType::INVALID);
+
+      Return.type = std::max(Return.type, Op.type);
+    }
+
+    return Return;
+  }
+
+  struct ValidatorResult visitUMaxExpr(const SCEVUMaxExpr* Expr) {
+    // We do not support unsigned operations. If 'Expr' is constant during Scop
+    // execution we treat this as a parameter, otherwise we bail out.
+    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
+      ValidatorResult Op = visit(Expr->getOperand(i));
+
+      if (!Op.isConstant())
+        return ValidatorResult(SCEVType::INVALID);
+    }
+
+    return ValidatorResult(SCEVType::PARAM);
+  }
+
+  ValidatorResult visitUnknown(const SCEVUnknown* Expr) {
+    Value *V = Expr->getValue();
+
+    if (isa<UndefValue>(V))
+      return ValidatorResult(SCEVType::INVALID);
+
+    if (BaseAddress) {
+      if (*BaseAddress)
+        return ValidatorResult(SCEVType::INVALID);
+      else
+        *BaseAddress = V;
+    }
+
+    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
+      if (R->contains(I))
+        return ValidatorResult(SCEVType::INVALID);
+
+    if (BaseAddress)
+      return ValidatorResult(SCEVType::PARAM);
+    else
+      return ValidatorResult(SCEVType::PARAM);
+  }
+};
+
+namespace polly {
+  bool isAffineExpr(const Region *R, const SCEV *Expr, ScalarEvolution &SE,
+                    Value **BaseAddress) {
+    if (isa<SCEVCouldNotCompute>(Expr))
+      return false;
+
+    if (BaseAddress)
+      *BaseAddress = NULL;
+
+    SCEVValidator Validator(R, SE, BaseAddress);
+    ValidatorResult Result = Validator.visit(Expr);
+
+    return Result.isValid();
+  }
+}
+
+