llvm dev - May 2017 - Computing loop trip counts with Scalar evolution

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?