Generalize IVUsers to track arbitrary expressions rather than expressions

explicitly split into stride-and-offset pairs. Also, add the
ability to track multiple post-increment loops on the same expression.

This refines the concept of "normalizing" SCEV expressions used for
to post-increment uses, and introduces a dedicated utility routine for
normalizing and denormalizing expressions.

This fixes the expansion of expressions which are post-increment users
of more than one loop at a time. More broadly, this takes LSR another
step closer to being able to reason about more than one loop at a time.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@100699 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 24 insertions, 42 deletions

diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index dc616ca2fd..a887c830c9 100644
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -16,6 +16,7 @@
 #define LLVM_ANALYSIS_IVUSERS_H
 
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Support/ValueHandle.h"
 
 namespace llvm {
@@ -26,17 +27,18 @@ class Value;
 class IVUsers;
 class ScalarEvolution;
 class SCEV;
+class IVUsers;
 
 /// IVStrideUse - Keep track of one use of a strided induction variable.
 /// The Expr member keeps track of the expression, User is the actual user
 /// instruction of the operand, and 'OperandValToReplace' is the operand of
 /// the User that is the use.
 class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
+  friend class IVUsers;
 public:
-  IVStrideUse(IVUsers *P, const SCEV *S, const SCEV *Off,
+  IVStrideUse(IVUsers *P, const SCEV *E,
               Instruction* U, Value *O)
-    : CallbackVH(U), Parent(P), Stride(S), Offset(Off),
-      OperandValToReplace(O), IsUseOfPostIncrementedValue(false) {
+    : CallbackVH(U), Parent(P), Expr(E), OperandValToReplace(O) {
   }
 
   /// getUser - Return the user instruction for this use.
@@ -53,23 +55,15 @@ public:
   /// this IVStrideUse.
   IVUsers *getParent() const { return Parent; }
 
-  /// getStride - Return the expression for the stride for the use.
-  const SCEV *getStride() const { return Stride; }
+  /// getExpr - Return the expression for the use.
+  const SCEV *getExpr() const { return Expr; }
 
-  /// setStride - Assign a new stride to this use.
-  void setStride(const SCEV *Val) {
-    Stride = Val;
+  /// setExpr - Assign a new expression to this use.
+  void setExpr(const SCEV *Val) {
+    Expr = Val;
   }
 
-  /// getOffset - Return the offset to add to a theoretical induction
-  /// variable that starts at zero and counts up by the stride to compute
-  /// the value for the use. This always has the same type as the stride.
-  const SCEV *getOffset() const { return Offset; }
-
-  /// setOffset - Assign a new offset to this use.
-  void setOffset(const SCEV *Val) {
-    Offset = Val;
-  }
+  const SCEV *getStride(const Loop *L) const;
 
   /// getOperandValToReplace - Return the Value of the operand in the user
   /// instruction that this IVStrideUse is representing.
@@ -83,37 +77,30 @@ public:
     OperandValToReplace = Op;
   }
 
-  /// isUseOfPostIncrementedValue - True if this should use the
-  /// post-incremented version of this IV, not the preincremented version.
-  /// This can only be set in special cases, such as the terminating setcc
-  /// instruction for a loop or uses dominated by the loop.
-  bool isUseOfPostIncrementedValue() const {
-    return IsUseOfPostIncrementedValue;
+  /// getPostIncLoops - Return the set of loops for which the expression has
+  /// been adjusted to use post-inc mode.
+  const PostIncLoopSet &getPostIncLoops() const {
+    return PostIncLoops;
   }
 
-  /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether
-  /// this is a post-increment use.
-  void setIsUseOfPostIncrementedValue(bool Val) {
-    IsUseOfPostIncrementedValue = Val;
-  }
+  /// transformToPostInc - Transform the expression to post-inc form for the
+  /// given loop.
+  void transformToPostInc(const Loop *L);
 
 private:
   /// Parent - a pointer to the IVUsers that owns this IVStrideUse.
   IVUsers *Parent;
 
-  /// Stride - The stride for this use.
-  const SCEV *Stride;
-
-  /// Offset - The offset to add to the base induction expression.
-  const SCEV *Offset;
+  /// Expr - The expression for this use.
+  const SCEV *Expr;
 
   /// OperandValToReplace - The Value of the operand in the user instruction
   /// that this IVStrideUse is representing.
   WeakVH OperandValToReplace;
 
-  /// IsUseOfPostIncrementedValue - True if this should use the
-  /// post-incremented version of this IV, not the preincremented version.
-  bool IsUseOfPostIncrementedValue;
+  /// PostIncLoops - The set of loops for which Expr has been adjusted to
+  /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept.
+  PostIncLoopSet PostIncLoops;
 
   /// Deleted - Implementation of CallbackVH virtual function to
   /// receive notification when the User is deleted.
@@ -174,18 +161,13 @@ public:
   /// return true.  Otherwise, return false.
   bool AddUsersIfInteresting(Instruction *I);
 
-  IVStrideUse &AddUser(const SCEV *Stride, const SCEV *Offset,
+  IVStrideUse &AddUser(const SCEV *Expr,
                        Instruction *User, Value *Operand);
 
   /// getReplacementExpr - Return a SCEV expression which computes the
   /// value of the OperandValToReplace of the given IVStrideUse.
   const SCEV *getReplacementExpr(const IVStrideUse &U) const;
 
-  /// getCanonicalExpr - Return a SCEV expression which computes the
-  /// value of the SCEV of the given IVStrideUse, ignoring the 
-  /// isUseOfPostIncrementedValue flag.
-  const SCEV *getCanonicalExpr(const IVStrideUse &U) const;
-
   typedef ilist<IVStrideUse>::iterator iterator;
   typedef ilist<IVStrideUse>::const_iterator const_iterator;
   iterator begin() { return IVUses.begin(); }