llvm dev - Apr 2019 - Loop Strength Reduction Pass Does Not Work for Some Varialbles Related to Induction Variables

Dear all,

    Hi! Recently, I try to combine the passes SeparateConstOffsetFromGEP and 
LoopStrengthReduction to transform the multiplication in the lowered GEP IRs
into addition.
    However, it seems LoopStrengthReduction is unable to remove all the
multiplications for the element offset calculation.
    My test code is shown below and thanks a lot in advance for your time and
suggestion!
-----------------------------------------------
#define NI 16
#define NJ 18
#define NK 22
#define NL 24
void kernel_2mm(int ni, int nj, int nk, int nl,
    int alpha,
    int beta,
    int tmp[NI][NJ],
    int A[NI][NK],
    int B[NK][NJ],
    int C[NJ][NL],
    int D[NI][NL])
{
  int i, j, k;

  /* D := alpha*A*B*C + beta*D */
  for (i = 0; i < NI; i++)
    for (j = 0; j < NJ; j++)
    {
        tmp[i][j] = 0;
        for (k = 0; k < NK; ++k)
          tmp[i][j] += alpha * A[i][k] * B[k][j];
    }
    for (i = 0; i < NI; i++)
      for (j = 0; j < NL; j++)
      {
        D[i][j] *= beta;
          for (k = 0; k < NJ; ++k)
            D[i][j] += tmp[i][k] * C[k][j];
      }
}




Best regards,
------------------------------------------
Tingyuan LIANG
MPhil Student
Department of Electronic and Computer Engineering
The Hong Kong University of Science and Technology
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190415/c1ffa43b/attachment-0001.html>

>From a quick glance at the code, it looks like both inner loops were
unrolled at least once (vary by architecture)
and have the expected number of multiplications, four and two (if unrolled
once), respectively.

https://gcc.godbolt.org/z/1ks4Pt

--
Momchil Velikov,
Senior Compiler Engineer
Arm
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190415/33ccc8fb/attachment.html>

Dear Momchil,

    Thanks a lot for your prompt reply and kindly suggestion.
    The code will truly lead to some automatic unrolling with GCC and increase
the number of operations in the assembly code. However, I am focus on the the IR
optimization and the calculation of the array element offest, which may need
multiplication if the IR instruction GEP is lowered to arithmetic operations.
The multiplication operations should be able to be removed by using the LLVM
Pass LoopStrengthReduction. Interestingly, it does not work for the test code.
    I wamt to post the IR code but it might be too long to be in the mail.
    Thanks again for your time and precious suggestions!

Best regards,
------------------------------------------
Tingyuan LIANG
MPhil Student
Department of Electronic and Computer Engineering
The Hong Kong University of Science and Technology



发件人: Momchil Velikov
发送时间: 4月16日星期二 01:13
主题: Re: [llvm-dev] Loop Strength Reduction Pass Does Not Work for Some
Varialbles Related to Induction Variables
收件人: Tingyuan LIANG
抄送: llvm-dev at lists.llvm.org


From a quick glance at the code, it looks like both inner loops were unrolled at
least once (vary by architecture)
and have the expected number of multiplications, four and two (if unrolled
once), respectively.

https://gcc.godbolt.org/z/1ks4Pt

--
Momchil Velikov,
Senior Compiler Engineer
Arm



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190415/1bc260bd/attachment.html>