[llvm-dev] Computing loop trip counts with Scalar evolution

[Andrew Santosa via llvm-dev]

I tried the analysis on the MatMul example, but the algorithm of http://stackoverflow.com/questions/13834364/how-to-get-loop-bounds-in-llvm did not return any trip count for any of the loops in MatMul using LLVM 3.4.2, which is quite old (complete sample analysis is here: https://github.com/analysis-examples/trip-counter), even if the bitcode input has been processed by mem2reg, as suggested here:https://groups.google.com/forum/#!topic/llvm-dev/1oNNBPMSqBg

I have not tried InnerLoopVectorizer::getOrCreateTripCount(), which is not there in LLVM 3.4.2.
I suppose I should first try using the latest LLVM release, but atm I'm having problems accessing llvm.org for download.

For the paper on SCEV, I have read 

O. Bachmann, P. S. Wang, and E. V. Zima. Chains of recurrences–to expedite the
evaluation of closed-form functions. In ISSAC ’94, pages 242–249. ACM, July 1994.

Best,
Andrew


On Friday, 19 May 2017, 3:03, via llvm-dev <llvm-dev at lists.llvm.org> wrote:



Message: 3

Date: Thu, 18 May 2017 21:30:33 +0300

From: Alex Susu via llvm-dev <llvm-dev at lists.llvm.org>

To: llvm-dev <llvm-dev at lists.llvm.org>

Subject: [llvm-dev] Computing loop trip counts with Scalar evolution

Message-ID: <079d36ea-a81f-5281-f26a-7ab7853a7b37 at gmail.com>

Content-Type: text/plain; charset=utf-8; format=flowed


   Hello.

     I tried to get the trip count of a loop with Scalar evolution. I got inspired from 

http://stackoverflow.com/questions/13834364/how-to-get-loop-bounds-in-llvm .

     However the analysis described there doesn't work well for the second inner loop of 

thes function below (although if we declare Bcols a short it works well):

       void MatMul(int Arows, int Acols, int Brows, int Bcols) {

         short i, j, k;

         for (i = 0; i < Arows; ++i) {

           for (j = 0; j < Bcols; ++j) {

             C[i][j] = 0;

             for (k = 0; k < Acols; ++k) {

               C[i][j] += A[i][k] * B[j][k];

             }

           }

         }

       }


     However, I discovered in LoopVectorize.cpp 

(http://llvm.org/docs/doxygen/html/LoopVectorize_8cpp_source.html) we have the method 

InnerLoopVectorizer::getOrCreateTripCount() that seems to do a better job at computing the 

trip count, even if the implementation differences are not big. The differences are subtle 

- first of all the method getOrCreateTripCount() doesn't call 

hasLoopInvariantBackedgeTakenCount().


     Please don't hesitate  to comment why InnerLoopVectorizer::getOrCreateTripCount() 

works better. I will try to come back myself with more info.


   Thank you,

     Alex


PS: Could you please recommend me one important paper for Scalar evolutions?