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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Amara Emerson via llvm-dev
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

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Loop Strength Reduction Pass Does Not Work for Some Varialbles Related to Induction Variables

Amara Emerson via llvm-dev
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.


--
Momchil Velikov,
Senior Compiler Engineer
Arm


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Loop Strength Reduction Pass Does Not Work for Some Varialbles Related to Induction Variables

Amara Emerson via llvm-dev
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
抄送: [hidden email]


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.

--
Momchil Velikov,
Senior Compiler Engineer
Arm




_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Loop Strength Reduction Pass Does Not Work for Some Varialbles Related to Induction Variables

Amara Emerson via llvm-dev

Some multiplications, used in address calculation, may stay after loop strength reduction, if the target machine has scaled index addressing mode.

--
Momchil Velikov,
Senior Compiler Engineer
Arm


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Loop Strength Reduction Pass Does Not Work for Some Varialbles Related to Induction Variables

Amara Emerson via llvm-dev
Dear Momchil,

    Thanks a lot for your detailed information and yes, it seems that loop strength reduction is limited by scaled index addressing mode. Now, I implement a simple LSR pass to do LSR aggressively, ignoring the scaled addressing mode.
    Thanks again for you time and suggestions!

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

From: Momchil Velikov <[hidden email]>
Sent: Tuesday, April 16, 2019 2:40 AM
To: Tingyuan LIANG
Cc: [hidden email]
Subject: Re: [llvm-dev] Loop Strength Reduction Pass Does Not Work for Some Varialbles Related to Induction Variables
 

Some multiplications, used in address calculation, may stay after loop strength reduction, if the target machine has scaled index addressing mode.

--
Momchil Velikov,
Senior Compiler Engineer
Arm


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev