delinearization of arrays

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

4 files changed, 19 insertions, 1 deletions

diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h
index 8fce2f6a9f..ea8cecf97e 100644
--- a/include/llvm/Analysis/DependenceAnalysis.h
+++ b/include/llvm/Analysis/DependenceAnalysis.h
@@ -908,6 +908,10 @@ namespace llvm {
     /// based on the current constraint.
     void updateDirection(Dependence::DVEntry &Level,
                          const Constraint &CurConstraint) const;
+
+    bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
+                        SmallVectorImpl<Subscript> &Pair) const;
+
   public:
     static char ID; // Class identification, replacement for typeinfo
     DependenceAnalysis() : FunctionPass(ID) {
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index 0b4e96f1e8..a5d098eb0d 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -136,6 +136,13 @@ namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
+  // createDelinearizationPass - This pass implements attempts to restore
+  // multidimensional array indices from linearized expressions.
+  //
+  FunctionPass *createDelinearizationPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   // Minor pass prototypes, allowing us to expose them through bugpoint and
   // analyze.
   FunctionPass *createInstCountPass();
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 1fc03be761..9cd902a120 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -351,8 +351,14 @@ namespace llvm {
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddRecExpr;
     }
-  };
 
+    /// Splits the SCEV into two vectors of SCEVs representing the subscripts
+    /// and sizes of an array access. Returns the remainder of the
+    /// delinearization that is the offset start of the array.
+    const SCEV *delinearize(ScalarEvolution &SE,
+                            SmallVectorImpl<const SCEV *> &Subscripts,
+                            SmallVectorImpl<const SCEV *> &Sizes) const;
+  };
 
   //===--------------------------------------------------------------------===//
   /// SCEVSMaxExpr - This class represents a signed maximum selection.
diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 68825a33a1..c650a6d76d 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -102,6 +102,7 @@ void initializeDSEPass(PassRegistry&);
 void initializeDebugIRPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
+void initializeDelinearizationPass(PassRegistry &);
 void initializeDependenceAnalysisPass(PassRegistry&);
 void initializeDomOnlyPrinterPass(PassRegistry&);
 void initializeDomOnlyViewerPass(PassRegistry&);