[prev in list] [next in list] [prev in thread] [next in thread] 

List:       llvm-dev
Subject:    [LLVMdev] [polly] scev codegen (first step to remove the dependence on ivcanon pass)
From:       Sebastian Pop <spop () codeaurora ! org>
Date:       2012-11-30 19:46:52
Message-ID: 20121130194652.GA27515 () codeaurora ! org
[Download RAW message or body]

Hi Tobi,

I would like to remove the SCEVRewriter code and replace it with a call to
SCEVAddRec::apply (see attached a patch that adds just this function).  More
precisely I want to add another function called apply_map that applies a map
(loop -> expr) on a given scev.  This is the apply function on a multi-variate
polynomial.

So here is an overview of how I would like the scev code generator to work on an
example: supposing that we have a Stmt_1 that gets code generated by either
CLooG or ISL-codegen like this:

  Stmt_1(c1, c1+4, c1+c2);

we will construct a map that maps the old iteration domain with 3 dimensions
(there are 3 arguments in Stmt_1 representing the original loop nest in which
Stmt_1 was located, let's call the original loop nest loop_1, loop_2, loop_3) to
the new expressions generated by cloog that are function of the new iteration
domain with 2 dimensions (c1 and c2 are the new induction variables of the code
generated by cloog).  So the content of that map is:

loop_1 -> c1
loop_2 -> c1+7
loop_3 -> c1+c2

Given an access function from the original program: 
  Scev_1 = {{{0, +, 4}_1, +, 5}_2, +, 6}_3

we will apply the map on it, and we will get a symbolic expression function of
the new induction variables c1, and c2:

Scev_2 = apply (loop_1 -> c1)    on Scev_1 = {{4*c1, +, 5}_2, +, 6}_3
Scev_3 = apply (loop_2 -> c1+7)  on Scev_2 = {4*c1 + 5*(c1+7), +, 6}_3
Scev_4 = apply (loop_3 -> c1+c2) on Scev_3 = 4*c1 + 5*(c1+7) + 6*(c1+c2)

We will then code generate Scev_4 and we will use this new expression for the
array access in the new loop nest.

Remark that in all this process we have never referred to the original
"canonical induction variable".  SCEV actually provides such a canonical form
for the induction variables without having to transform the code.

Sebastian
-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation

["0001-add-SCEVAddRecExpr-apply.patch" (text/x-diff)]

From c4307bfa54a430e8d5715cefd9ea3675b6980de5 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <spop@codeaurora.org>
Date: Wed, 28 Nov 2012 17:29:58 -0600
Subject: [PATCH] add SCEVAddRecExpr::apply

---
 include/llvm/Analysis/ScalarEvolutionExpressions.h |    5 +++++
 lib/Analysis/ScalarEvolution.cpp                   |   19 +++++++++++++++++++
 2 files changed, 24 insertions(+), 0 deletions(-)

diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h \
b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 54db7d6..9083527 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -332,6 +332,11 @@ namespace llvm {
     /// the specified iteration number.
     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
 
+    /// Return the chain of recurrences obtained by applying X to the current
+    /// chain of recurrences in the given loop L.  For example:
+    /// apply({{5, +, 3}_loop1, +, 2}_loop2, X, loop_1) -> {3*X+5, +, 2}_loop2
+    const SCEV *apply(const SCEV *X, Loop *L, ScalarEvolution &SE) const;
+
     /// getNumIterationsInRange - Return the number of iterations of this loop
     /// that produce values in the specified constant range.  Another way of
     /// looking at this is that it returns the first iteration number where the
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 5f60bd1..d7fd7ba 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -811,6 +811,25 @@ const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
   return Result;
 }
 
+/// Return the chain of recurrences obtained by applying X to the current
+/// chain of recurrences in the given loop L.  For example:
+/// apply({{5, +, 3}_loop1, +, 2}_loop2, X, loop_1) -> {3*X+5, +, 2}_loop2
+const SCEV *SCEVAddRecExpr::apply(const SCEV *X, Loop *L,
+                                  ScalarEvolution &SE) const {
+  if (L == getLoop())
+    return evaluateAtIteration(X, SE);
+
+  SmallVector<const SCEV *, 2> Operands;
+  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+    if (isa<SCEVAddExpr>(getOperand(I)))
+      Operands.push_back(apply(getOperand(I), L, SE));
+    else
+      Operands.push_back(getOperand(I));
+
+  return SE.getAddRecExpr(Operands, getLoop(), getNoWrapFlags(FlagNW));
+}
+
+
 //===----------------------------------------------------------------------===//
 //                    SCEV Expression folder implementations
 //===----------------------------------------------------------------------===//
-- 
1.7.6.4



_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


[prev in list] [next in list] [prev in thread] [next in thread]