[SCEV] Support GEP in createSimpleAffineAddRec() (NFCI)

[nikic]

Summary

Currently, all GEP addrecs go through the generic createAddRecFromPHI() code. I think it would make sense to support at least basic constant increment GEPs in createSimpleAffineAddRec(), which is what this patch implements.

This gives a pretty small compile-time improvement: http://llvm-compile-time-tracker.com/compare.php?from=f30f34e6ba411c43315f9065860a51c23ce4136a&to=446d1e1504232493002f3b7c4d436e35e5965c86&stat=instructions:u Maybe it's not worth it.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5710

Any reason why not NSW?

[mkazantsev]

Is it possible to create a unit test?

llvm/lib/Analysis/ScalarEvolution.cpp

 /// technique for finding the AddRec expression.
 const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
                                                       Value *BEValueV,
                                                       Value *StartValueV) {
   const Loop *L = LI.getLoopFor(PN->getParent());
   assert(L && L->getHeader() == PN->getParent());
   assert(BEValueV && StartValueV);
 
-  auto BO = MatchBinaryOp(BEValueV, getDataLayout(), AC, DT, PN);
-  if (!BO)
-    return nullptr;
-
-  if (BO->Opcode != Instruction::Add)
-    return nullptr;
-
   const SCEV *Accum = nullptr;
+  SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
+
+  const DataLayout &DL = getDataLayout();
+  auto BO = MatchBinaryOp(BEValueV, DL, AC, DT, PN);
+  if (BO && BO->Opcode == Instruction::Add) {
     if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
       Accum = getSCEV(BO->RHS);
     else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
       Accum = getSCEV(BO->LHS);
-
-  if (!Accum)
+    else
       return nullptr;
 
-  SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
     if (BO->IsNUW)
       Flags = setFlags(Flags, SCEV::FlagNUW);
     if (BO->IsNSW)
       Flags = setFlags(Flags, SCEV::FlagNSW);
+  } else if (auto *GEP = dyn_cast<GetElementPtrInst>(BEValueV);
+             GEP && GEP->getPointerOperand() == PN &&
+             GEP->hasAllConstantIndices()) {
+    APInt Offset(DL.getIndexTypeSizeInBits(PN->getType()), 0);
+    if (!GEP->accumulateConstantOffset(DL, Offset))
+      return nullptr;
+    Accum = getConstant(Offset);
+    if (GEP->isInBounds()) {
+      Flags = setFlags(Flags, SCEV::FlagNW);
+      if (Offset.isNonNegative())
+        Flags = setFlags(Flags, SCEV::FlagNUW);
+    }
+  } else {
+    return nullptr;
+  }
 
   const SCEV *StartVal = getSCEV(StartValueV);
   const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
   insertValueToMap(PN, PHISCEV);
 
   if (auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
     setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR),
                    (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |