[SCEV] Introduce SCEVPostIncRewriter

[skatkov]

Summary

The patch introduces the SCEVPostIncRewriter rewriter which
is similar to SCEVInitRewriter but rewrites AddRec with post increment
value of this AddRec.

This is a preparation for re-writing isKnownPredicate utility as
described in https://reviews.llvm.org/D42417.

[sanjoy]

Same comment at https://reviews.llvm.org/D43498#1012884

[skatkov]

Please take a look.

[sanjoy]

lgtm with minor fixes

lib/Analysis/ScalarEvolution.cpp

4142 ↗

(On Diff #135013)

We don't need IgnoreOtherLoops right? If so, let's remove it for now.

4166 ↗

(On Diff #135013)

This should be called something more descriptive -- perhaps SawLoopVariantSCEVUnknown or something like that.

Also applies to D43498

4168 ↗

(On Diff #135013)

s/isSeenOtherLoops/hasSeenOtherLoops/

Also applies to D43498

[skatkov]

lib/Analysis/ScalarEvolution.cpp

4142 ↗

(On Diff #135013)

If I understood it correctly the idea is just to remove it for now to make patch mostly NFC (related to D43498) and add it when we need it in "IsKnownPredicated Fix" patch. Ok, I'll do that.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

4142 ↗

(On Diff #135013)

No, I meant always have the behavior be to ignore other loops (so you don't have to change anything in D43498).

You might also want to change SCEVInitRewriter default IgnoreOtherLoops to true for consistency.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

private:
   explicit SCEVInitRewriter(const Loop *L, ScalarEvolution &SE)
       : SCEVRewriteVisitor(SE), L(L) {}
 
   const Loop *L;
   bool SeenLoopVariantSCEVUnknown = false;
   bool SeenOtherLoops = false;
 };
 
+/// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
+/// increment expression in case its Loop is L. If it is not L then
+/// use AddRec itself.
+/// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
+class SCEVPostIncRewriter : public SCEVRewriteVisitor<SCEVPostIncRewriter> {
+public:
+  static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) {
+    SCEVPostIncRewriter Rewriter(L, SE);
+    const SCEV *Result = Rewriter.visit(S);
+    return Rewriter.hasSeenLoopVariantSCEVUnknown()
+        ? SE.getCouldNotCompute()
+        : Result;
+  }
+
+  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+    if (!SE.isLoopInvariant(Expr, L))
+      SeenLoopVariantSCEVUnknown = true;
+    return Expr;
+  }
+
+  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
+    // Only re-write AddRecExprs for this loop.
+    if (Expr->getLoop() == L)
+      return Expr->getPostIncExpr(SE);
+    SeenOtherLoops = true;
+    return Expr;
+  }
+
+  bool hasSeenLoopVariantSCEVUnknown() { return SeenLoopVariantSCEVUnknown; }
+
+  bool hasSeenOtherLoops() { return SeenOtherLoops; }
+
+private:
+  explicit SCEVPostIncRewriter(const Loop *L, ScalarEvolution &SE)
+      : SCEVRewriteVisitor(SE), L(L) {}
+
+  const Loop *L;
+  bool SeenLoopVariantSCEVUnknown = false;
+  bool SeenOtherLoops = false;
+};
+
 /// This class evaluates the compare condition by matching it against the
 /// condition of loop latch. If there is a match we assume a true value
 /// for the condition while building SCEV nodes.
 class SCEVBackedgeConditionFolder
     : public SCEVRewriteVisitor<SCEVBackedgeConditionFolder> {
 public:
   static const SCEV *rewrite(const SCEV *S, const Loop *L,
                              ScalarEvolution &SE) {