[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

4138

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

4162

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

Also applies to D43498

4164

s/isSeenOtherLoops/hasSeenOtherLoops/

Also applies to D43498

[skatkov]

lib/Analysis/ScalarEvolution.cpp

4138

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

4138

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

explicit SCEVInitRewriter(const Loop *L, ScalarEvolution &SE,
                             bool IgnoreOtherLoops)
       : SCEVRewriteVisitor(SE), L(L), IgnoreOtherLoops(IgnoreOtherLoops) {}
 
   const Loop *L;
   const bool IgnoreOtherLoops;
   bool Valid = true;
 };
 
+/// 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, IgnoreOtherLoops);
+    const SCEV *Result = Rewriter.visit(S);
+    return Rewriter.isValid() ? Result : SE.getCouldNotCompute();
+  }
+
+  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+    if (!SE.isLoopInvariant(Expr, L))
+      Valid = false;
+    return Expr;
+  }
+
+  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
+    // Only allow AddRecExprs for this loop.
+    if (Expr->getLoop() == L)
+      return Expr->getPostIncExpr(SE);
+    // If we should not ignore other loops then invalidate result.
+    Valid = Valid && IgnoreOtherLoops;
+    return Expr;
+  }
+
+  bool isValid() { return Valid; }
+
+private:
+  explicit SCEVPostIncRewriter(const Loop *L, ScalarEvolution &SE,
+                               bool IgnoreOtherLoops)
+      : SCEVRewriteVisitor(SE), L(L), IgnoreOtherLoops(IgnoreOtherLoops) {}
+
+  const Loop *L;
+  const bool IgnoreOtherLoops;
+  bool Valid = true;
+};
+
 /// 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) {