Progress in adding a data prefetching transformation to LLVM Polly - the summer of code project

[Jun-qi Deng]

GSOC2012 Project: Adding a data prefetching transformation to LLVM Polly – generating load-balanced and coarse-grain loop pipelinable code for more task level parallelism and data locality (Done and Todo)

 

Hi all! I want to make a post here about the recent progress of my project "adding a data prefetching transformation to LLVM Polly". Here's the done and todo list.

 

Done:

1)  Add to polly a polly-pipfor pass, which initially implements most of the analysis part of the Google Summer of Code 2012 proposal: Adding a data prefetching transformation to LLVM Polly – generating load-balanced and coarse-grain loop pipelinable code for more task level parallelism and data locality http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/tangkk/1
For the moment, this pass can: a) Extract the HEAD(which is a vector of those read memory accesses), FOOT(which is a vector of those write memory accesses) and BODY(which is a vector of those instructions occur between a pair of load and store); b) Tell the RAW or WAR dependence distances of those read or write memory accesses within the same scopstmt; c)Provide the instruction of each memory access; d)Brief calculate the LoadAnalysis claimed at the proposal(but it seems not a good idea to do so in the llvm IR level, so we may left this method here and add better things inside afterwards)
You can see inside the following testcases for more detail about the analysis result.

2)  Add a Pipfor folder that contains 12 testcases, which can represent many types of loop, for this pass:
test/Pipfor/2mm.ll           
test/Pipfor/3mm.ll           
 test/Pipfor/RAW_loop.ll      
test/Pipfor/WAR_loop.ll     
test/Pipfor/correlation.ll   
  test/Pipfor/covariance.ll    
 test/Pipfor/matmul.ll        
 test/Pipfor/sim2mm.ll        
test/Pipfor/simatax.ll       
 test/Pipfor/simbicg.ll       
test/Pipfor/simdoitgen.ll    
test/Pipfor/simple_loop.ll   

All of these, except for the simbicg.ll, pass the test. Only simbicg.ll is expected to fail. The test begins with “sim” is a paraphrase of the Polybench test cases for simplicity, for example, sim2mm is a paraphrase of 2mm.The “sim” version discards the kernel function call and replaces it with an inline kernel within the main function.

3)  This analyzed pass is invoked through “-polly-pipfor” option when individually schedule the polly passes, for example:
opt -S -mem2reg -loop-simplify -indvars $LLVMASM > $LLVMIR
opt -basicaa -polly-prepare -polly-region-simplify -polly-detect -polly-pipfor -analyze $LLVMIR

And it is invoked through “-polly-piploop” option when loading polly into clang and automatically run it at -O3,for example:
pollycc -O3 -mllvm -polly $SOURCE -mllvm -polly-piploop –mllvm

The patches are attached. Note that:

*   Patch 0001 adds four helper functions for isl_aff and isl_pw_aff.

*   Patch 0002 adds a getInstructionFor method to return the memory access instruction.

*   Patch 0003 is the patch for the Pipfor Pass. It implements those things mentioned above.

*   Patch 0004 is the patch for testcases.

 

Todo:

1)  Separate the pass into several small commits that are logical related so as to be better reviewed

2)  More different types of testcases. Write some guard statements to judge those cases that cannot be dealt with for the moment

3)  Implement fine-grain statement

4)  Include indirect dependence analysis

5)  A webpage that shows the up-to-date progress or status of this project

6)  If possible, the codegen part of my proposal.

[Jun-qi Deng]

Hi Tobi! I've already make a webpage patch about this summer of code project. Please see the attachment.

best regards,

tangkk

2012/6/27 Jun-qi Deng <dengjunq...@gmail.com>

[Hongbin Zheng]

Hi Junqi,

About the patch [PATCH 1/4] Add GICHelper Support for isl_aff and isl_pw_aff.

+
+std::string polly::stringFromIslObj(/*__isl_keep*/isl_aff *aff) {
Please add a space between /*__isl_keep*/ and isl_aff, so it become:
+std::string polly::stringFromIslObj(/*__isl_keep*/ isl_aff *aff) {

This should also apply to the rest functions.

You may also find that you almost create these functions by copy and
paste, so a better way is use template or macro, e.g.

In GICHelper.cpp you can write a generic internal function template:

template<typename ISLTy, typename ISL_CTX_GETTER, typename ISL_PRINTER>
static inline std::string stringFromIslObjInternal(/*__isl_keep*/
ISLTy *isl_obj, ISL_CTX_GETTER ctx_getter_fn, ISL_PRINTER printer_fn)
{
isl_ctx *ctx = ctx_getter_fn(isl_obj);
isl_printer *p = isl_printer_to_str(ctx);
printer_fn(p, isl_obj);
char *char_str = isl_printer_get_str(p);
std::string string(char_str);
free(char_str);
isl_printer_free(p);
return string;
}

After you have this function template, you can impelement the original
stringFromIslObj like this:

std::string polly::stringFromIslObj(/*__isl_keep*/ isl_multi_aff *maff) {
return stringFromIslObjInternal(maff, isl_multi_aff_get_ctx,
isl_printer_print_multi_aff);
}

std::string polly::stringFromIslObj(/*__isl_keep*/ isl_pw_multi_aff *pma) {
return stringFromIslObjInternal(pma, sl_pw_multi_aff_get_ctx,
isl_printer_print_pw_multi_aff);
}

...

best regards
ether

[Hongbin Zheng]

Hi JunQi,

Regarding to the patch "[PATCH 2/4] Add
getInstructionFor(MemoryAccess* MemAccs) Method":
---
include/polly/ScopInfo.h | 5 +++++
lib/Analysis/ScopInfo.cpp | 1 +
2 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h
index 4eb1ece..53aaea8 100755
--- a/include/polly/ScopInfo.h
+++ b/include/polly/ScopInfo.h
@@ -251,6 +251,7 @@ class ScopStmt {
typedef SmallVector<MemoryAccess*, 8> MemoryAccessVec;
MemoryAccessVec MemAccs;
std::map<const Instruction*, MemoryAccess*> InstructionToAccess;
+ std::map<MemoryAccess*, const Instruction*> AccessToInstruction;

//@}

@@ -327,6 +328,10 @@ public:
return at == InstructionToAccess.end() ? NULL : at->second;
}

+ const Instruction *getInstructionFor(MemoryAccess* MemAccs) {
+ return AccessToInstruction[MemAccs];
+ }
+
void setBasicBlock(BasicBlock *Block) { BB = Block; }

typedef MemoryAccessVec::iterator memacc_iterator;
diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp
index 7c5ce1d..19ef8a0 100644
--- a/lib/Analysis/ScopInfo.cpp
+++ b/lib/Analysis/ScopInfo.cpp
@@ -504,6 +504,7 @@ void ScopStmt::buildAccesses(TempScop &tempScop,
const Region &CurRegion) {
E = AccFuncs->end(); I != E; ++I) {
MemAccs.push_back(new MemoryAccess(I->first, this));
InstructionToAccess[I->second] = MemAccs.back();
+ AccessToInstruction[MemAccs.back()] = I->second;
}
}

--
1.7.5.1

I perfer to remember the accessing instruction in the MemoryAccess
class, instead of creating another map in ScopStmt.

best regards
ether

[Tobias Grosser]

ether is right here. We should be able to reduce code duplication here.

ether, can you review the upcoming version and commit it it is ready? I
don't think I am needed for this. ;-)

Tobi

[Tobias Grosser]

On 07/03/2012 10:37 AM, Hongbin Zheng wrote:
> Hi JunQi,
>
> Regarding to the patch "[PATCH 2/4] Add
> getInstructionFor(MemoryAccess* MemAccs) Method":

[..]

>
> I perfer to remember the accessing instruction in the
> MemoryAccess class, instead of creating another map in ScopStmt. best
> regards ether

I agree with ether, just add a member variable to the MemoryAccess class.

ether, you can commit such a patch after you reviewed it directly. No
need to wait for my response.

Tobi

[Hongbin Zheng]

Ok.
>
> Tobi

[Jun-qi Deng]

Hi ether! Here are two patches for the GICHelper according to your advices. Please review. :)

best regards,

tangkk

[Hongbin Zheng]

Hi JunQi,

---
lib/Support/GICHelper.cpp | 69 ++++++++++++++++++++------------------------
1 files changed, 31 insertions(+), 38 deletions(-)

diff --git a/lib/Support/GICHelper.cpp b/lib/Support/GICHelper.cpp
index 46184f3..67f434b 100644
--- a/lib/Support/GICHelper.cpp
+++ b/lib/Support/GICHelper.cpp
@@ -60,46 +60,39 @@ APInt polly::APInt_from_MPZ (const mpz_t mpz) {
}
}

-std::string polly::stringFromIslObj(/*__isl_keep*/ isl_map *map) {
- isl_printer *p = isl_printer_to_str(isl_map_get_ctx(map));
- isl_printer_print_map(p, map);
- char *char_str = isl_printer_get_str(p);
- std::string string(char_str);
- free(char_str);
- isl_printer_free(p);
- return string;
-}
-
-std::string polly::stringFromIslObj(/*__isl_keep*/ isl_set *set) {
- isl_printer *p = isl_printer_to_str(isl_set_get_ctx(set));
- isl_printer_print_set(p, set);
- char *char_str = isl_printer_get_str(p);
- std::string string(char_str);
- free(char_str);
- isl_printer_free(p);
- return string;
-}
-
-std::string polly::stringFromIslObj(/*__isl_keep*/ isl_union_map *umap) {
- isl_printer *p = isl_printer_to_str(isl_union_map_get_ctx(umap));
- isl_printer_print_union_map(p, umap);
- char *char_str = isl_printer_get_str(p);
- std::string string(char_str);
- free(char_str);
- isl_printer_free(p);
- return string;
-}
-
-std::string polly::stringFromIslObj(/*__isl_keep*/ isl_union_set *uset) {
- isl_printer *p = isl_printer_to_str(isl_union_set_get_ctx(uset));
- isl_printer_print_union_set(p, uset);
- char *char_str = isl_printer_get_str(p);
- std::string string(char_str);
- free(char_str);
- isl_printer_free(p);
- return string;
+template<typename ISLTy, typename ISL_CTX_GETTER, typename ISL_PRINTER>
+static inline std::string stringFromIslObjInternal(/*__isl_keep*/
+ ISLTy *isl_obj, ISL_CTX_GETTER ctx_getter_fn, ISL_PRINTER printer_fn) {
+ isl_ctx *ctx = ctx_getter_fn(isl_obj);
+ isl_printer *p = isl_printer_to_str(ctx);
+ printer_fn(p, isl_obj);
+ char *char_str = isl_printer_get_str(p);
+ std::string string(char_str);
+ free(char_str);
+ isl_printer_free(p);
+ return string;
}

+std::string polly::stringFromIslObj(/*__isl_keep*/ isl_map *map) {
+ return stringFromIslObjInternal(map, isl_map_get_ctx,
+ isl_printer_print_map);
+}
+
+std::string polly::stringFromIslObj(/*__isl_keep*/ isl_set *set) {
+ return stringFromIslObjInternal(set, isl_set_get_ctx,
+ isl_printer_print_set);
----------------------------------------------------------------------------------------------------------
please align the indent like this:
return stringFromIslObjInternal(set, isl_set_get_ctx,
isl_printer_print_set);


+}
+
+std::string polly::stringFromIslObj(/*__isl_keep*/ isl_union_map *umap) {
+ return stringFromIslObjInternal(umap, isl_union_map_get_ctx,
+ isl_printer_print_union_map);
+}
+
+std::string polly::stringFromIslObj(/*__isl_keep*/ isl_union_set *uset) {
+ return stringFromIslObjInternal(uset, isl_union_set_get_ctx,
+ isl_printer_print_union_set);
+}
+
std::string polly::stringFromIslObj(/*__isl_keep*/ isl_schedule *schedule) {
isl_ctx *ctx = isl_union_map_get_ctx(isl_schedule_get_map(schedule));
isl_printer *p = isl_printer_to_str(ctx);
----------------------------------------------------------------------------------------------------------
What about this function? You may create another helperfunction:
static inline isl_ctx *get_schedule_ctx(/*__isl_keep*/ isl_schedule
*schedule) {
return isl_union_map_get_ctx(isl_schedule_get_map(schedule));
}

With this function, you can also fix this function by:
std::string polly::stringFromIslObj(/*__isl_keep*/ isl_schedule *schedule) {
return stringFromIslObjInternal(schedule, get_schedule_ctx,
......);
}

--
best regards
ether

[Jun-qi Deng]

Hi ether! I've already fixed the related patches accordingly. Please review... And I'm going to do those in the todo list.

best regards,

tangkk

2012/7/5 Hongbin Zheng <ethe...@gmail.com>

[Hongbin Zheng]

Hi Junqi,


Regarding [PATCH 3/6] Add getInstructionFor(MemoryAccess* MemAccs) Method:

---
include/polly/ScopInfo.h | 14 ++++++++++++++
lib/Analysis/ScopInfo.cpp | 5 +++++
2 files changed, 19 insertions(+), 0 deletions(-)

diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h
index 9bb08ef..71a2643 100755
--- a/include/polly/ScopInfo.h
+++ b/include/polly/ScopInfo.h
@@ -102,6 +102,8 @@ private:
void setBaseName();
ScopStmt *statement;

+ const Instruction *Inst;
--------------------------------------------------------------------------------------------------
We should also initialize this member variable in the constructor of
the MemoryAccess.
Which means we need to modifiy the constructor so that it also accept
the a pointer to Instruction as argument and
initialize Inst by the in coming pointer.
+
/// Updated access relation read from JSCOP file.
isl_map *newAccessRelation;
public:
@@ -136,6 +138,10 @@ public:
return BaseName;
}

+ const Instruction *getAccessInstruction() const {
+ return Inst;
+ }
+
/// @brief Get the new access function imported from JSCOP file
isl_map *getNewAccessRelation() const;

@@ -160,6 +166,9 @@ public:
/// @brief Set the updated access relation read from JSCOP file.
void setNewAccessRelation(isl_map *newAccessRelation);

+ /// @brief Set the Instruction of this memory access
+ void setAccessInstruction(const Instruction *AccInst);
+
/// @brief Align the parameters in the access relation to the scop context
void realignParams();

@@ -251,6 +260,7 @@ class ScopStmt {

typedef SmallVector<MemoryAccess*, 8> MemoryAccessVec;
MemoryAccessVec MemAccs;
std::map<const Instruction*, MemoryAccess*> InstructionToAccess;
+ std::map<MemoryAccess*, const Instruction*> AccessToInstruction;

--------------------------------------------------------------------------------------------------------
After a MemoryAccess can remember the underlying access instruction,
this map is not needed anymore.

//@}

@@ -327,6 +337,10 @@ public:

return at == InstructionToAccess.end() ? NULL : at->second;
}

+ const Instruction *getInstructionFor(MemoryAccess* MemAccs) {
+ return AccessToInstruction[MemAccs];
+ }
+
void setBasicBlock(BasicBlock *Block) { BB = Block; }

typedef MemoryAccessVec::iterator memacc_iterator;
diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp

index cc3c24f..d3875b0 100644
--- a/lib/Analysis/ScopInfo.cpp
+++ b/lib/Analysis/ScopInfo.cpp
@@ -445,6 +445,10 @@ void MemoryAccess::setNewAccessRelation(isl_map
*newAccess) {
newAccessRelation = newAccess;
}

+void MemoryAccess::setAccessInstruction(const Instruction *AccInst) {
+ Inst = AccInst;
+}
+
//===----------------------------------------------------------------------===//

isl_map *ScopStmt::getScattering() const {
@@ -489,6 +493,7 @@ void ScopStmt::buildAccesses(TempScop &tempScop,

const Region &CurRegion) {
E = AccFuncs->end(); I != E; ++I) {
MemAccs.push_back(new MemoryAccess(I->first, this));

---------------------------------------------------------------------------------------------
After we modify This line should looks like this:

MemAccs.push_back(new MemoryAccess(I->first, I->second, this));

InstructionToAccess[I->second] = MemAccs.back();
+ AccessToInstruction[MemAccs.back()] = I->second;
}
}

best regards
ether

[Jun-qi Deng]

Hi ether! Thank you for this detailed advises. I've fixed the patch and change its commit message. Please see.

best regards,

tangkk

2012/7/5 Hongbin Zheng <ethe...@gmail.com>

Hi Junqi,

[Jun-qi Deng]

Hi ether! I've fixed my "Pipfor" patch. Now it becomes simply a frame structure of the Pipfor Analysis. After you've checked this, I will add the members and functions into this frame step by step according to your advice. Thank you!!

best regards,

tangkk

[Jun-qi Deng]

Hi ether! Here is a patch following the above two. This patch fills the AnalyzeOnInnermostLoop function based on two classes: Memref and PipforNode. Please review.

best regards,

tangkk

[Jun-qi Deng]

Hi, here I found that the right way to print the isl_schedule is to use:

std::string polly::stringFromIslObj(/*__isl_keep*/ isl_schedule *schedule) {

  return stringFromIslObjInternal(schedule, isl_schedule_get_ctx,

                                  isl_printer_print_schedule);

}

Otherwise, it will get errors.

and here is the patch.

best regards,

tangkk

[Hongbin Zheng]

Thanks for the patch,

Besides, A trivial test case to demonstrate this bug would be great.

[Jun-qi Deng]

Thanks for the patch,

Besides, A trivial test case to demonstrate this bug would be great.

But I'm afraid that I can't provide any, because Polly does not contain any code that uses "std::string polly::stringFromIslObj(/*__isl_keep*/ isl_schedule *schedule)". I found this bug because I use it for some reason, but I can find nowhere else in the source code use this method. To trigger this bug, just simply put "dbgs() << "Schedule:\n" << stringFromIslObj(Schedule) << "\n";" anywhere within the scope an isl_schedule, for example within the IslScheduleOptimizer::getScheduleMap.

best regards,

tangkk

[Tobias Grosser]

On 06/28/2012 11:07 AM, Jun-qi Deng wrote:
> Hi Tobi! I've already make a webpage patch about this summer of code
> project. Please see the attachment.

Hi tangkk,

I am very late on this. The website looks nice, but it misses a header
that this is still a work in progress SoC project. Would you mind adding
such a header and updating it. I think it can than be committed
be me or either to the website.

Tobi

[Jun-qi Deng]

Hi Tobi! I'm working on the loop nest tree analysis now and the outcome is ready to be presented soon. OK, because the path I'm undertaking now has changed a little, I will arrange every thing I did again and fix that website.

regards,

tangkk

2012/8/7 Tobias Grosser <tob...@grosser.es>