[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

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

4166

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

Also applies to D43498

4168

s/isSeenOtherLoops/hasSeenOtherLoops/

Also applies to D43498

[skatkov]

lib/Analysis/ScalarEvolution.cpp

4142

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

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.

lib/Analysis/ScalarEvolution.cpp

private:
   explicit SCEVInitRewriter(const Loop *L, ScalarEvolution &SE)
       : SCEVRewriteVisitor(SE), L(L) {}
 
   const Loop *L;
   bool Valid = true;
   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
+/// if IgnoreOtherLoops is true then use AddRec itself
+/// otherwise rewrite cannot be done.
+/// 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,
+                             bool IgnoreOtherLoops = false) {
+    SCEVPostIncRewriter Rewriter(L, SE);
+    const SCEV *Result = Rewriter.visit(S);
+    if (!Rewriter.isValid())
+      return SE.getCouldNotCompute();
+    return Rewriter.isSeenOtherLoops() && !IgnoreOtherLoops
+               ? SE.getCouldNotCompute()
+               : Result;
+  }
+
+  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+    if (!SE.isLoopInvariant(Expr, L))
+      Valid = false;
+    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 isValid() { return Valid; }
+
+  bool isSeenOtherLoops() { return SeenOtherLoops; }
+
+private:
+  explicit SCEVPostIncRewriter(const Loop *L, ScalarEvolution &SE)
+      : SCEVRewriteVisitor(SE), L(L) {}
+
+  const Loop *L;
+  bool Valid = true;
+  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) {