Add support for srem instruction

Remainder operations with constant divisor can be modeled as quasi-affine
expression. This patch adds support for detecting and modeling them. We also
add a test that ensures they are correctly code generated.

This patch was extracted from a larger patch contributed by Johannes Doerfert
in http://reviews.llvm.org/D5293

llvm-svn: 240518
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
index b06e8be..2092047 100644
--- a/polly/lib/Support/SCEVValidator.cpp
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -349,6 +349,20 @@
     return visit(DividendSCEV);
   }
 
+  ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
+    assert(SRem->getOpcode() == Instruction::SRem &&
+           "Assumed SRem instruction!");
+
+    auto *Divisor = SRem->getOperand(1);
+    auto *CI = dyn_cast<ConstantInt>(Divisor);
+    if (!CI)
+      return visitGenericInst(SRem, S);
+
+    auto *Dividend = SRem->getOperand(0);
+    auto *DividendSCEV = SE.getSCEV(Dividend);
+    return visit(DividendSCEV);
+  }
+
   ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
     Value *V = Expr->getValue();
 
@@ -371,6 +385,8 @@
       switch (I->getOpcode()) {
       case Instruction::SDiv:
         return visitSDivInstruction(I, Expr);
+      case Instruction::SRem:
+        return visitSRemInstruction(I, Expr);
       default:
         return visitGenericInst(I, Expr);
       }