llvm dev - Jan 2018 - Source level code transformation V.S. IR-level code transformation

Dear all,
    I'm working on a simple code transformation problem that can be
described as below:

    for a C++ loop:

    *for (int i = 0; i < N; ++i) {*
*        a = M[i] + b;*
*    }*

    I want to transform it to:

    *int A[4];    *

*    for (int i = 0; i < N; ++i) {*
*        A[0] = M[i] + b;*
*        A[1] = M[i] + b;*
*        A[2] = M[i] + b;*
*        A[3] = M[i] + b;*
*    }*

   The reason I want to do it is to transform my code to a form that SLP
vectorizer is able to vectorize it.

   I know there are a few approaches for transforming the code, the
simplest being a naive text processor for duplicating the assignment
instructions in the loop, but I don't think it a standard way for code
transformation.

   I also got to know a few other alternatives:

   1. using libTooling to edit the AST
   2. transform the IR code of the loop, in a PASS, so that the SLP PASS
   can consume the resulting IR

   Does anyone know which alternative is the most used or most standard way
of doing such a transformation work? Thanks!
-- 
Sincerely,
Linchuan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180114/b850231e/attachment.html>

2018-01-15 9:36 GMT+08:00 Linchuan Chen via llvm-dev <
llvm-dev at lists.llvm.org>:
> Dear all,
>     I'm working on a simple code transformation problem that can be
> described as below:
>
>     for a C++ loop:
>
>     *for (int i = 0; i < N; ++i) {*
> *        a = M[i] + b;*
> *    }*
>
>     I want to transform it to:
>
>     *int A[4];    *
>
> *    for (int i = 0; i < N; ++i) {*
> *        A[0] = M[i] + b;*
> *        A[1] = M[i] + b;*
> *        A[2] = M[i] + b;*
> *        A[3] = M[i] + b;*
> *    }*
>
​The transformed code should be

    *int A[4];    *

*    for (int i = 0; i < N; i+=4) {*
*        A[0] = M[i] + b;*
*        A[1] = M[i+1] + b;*
*        A[2] = M[i+2] + b;*
*        A[3] = M[i+3] + b;*
*    }*

​I would suggest you manually rewrite the code, and see if SLP works on it.
I think doing the transformation in source level would be easier. Or you
can observe the IR for both side, see if you can think of algorithm
handling your case.

-- 
Wei-Ren Chen (陳韋任)
Homepage: https://people.cs.nctu.edu.tw/~chenwj
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180115/79f75553/attachment.html>

Thanks Weiren!

    My goal is to transform the code automatically by doing some code
analysis, instead of rewriting it manually.

    To do this source level auto transformation, do you have any
suggestions on what tool to use? Thanks again!!

On Mon, Jan 15, 2018 at 04:25 陳韋任 via llvm-dev <llvm-dev at
lists.llvm.org>
wrote:
> 2018-01-15 9:36 GMT+08:00 Linchuan Chen via llvm-dev <
> llvm-dev at lists.llvm.org>:
>
>> Dear all,
>>     I'm working on a simple code transformation problem that can be
>> described as below:
>>
>>     for a C++ loop:
>>
>>     *for (int i = 0; i < N; ++i) {*
>> *        a = M[i] + b;*
>> *    }*
>>
>>     I want to transform it to:
>>
>>     *int A[4];    *
>>
>> *    for (int i = 0; i < N; ++i) {*
>> *        A[0] = M[i] + b;*
>> *        A[1] = M[i] + b;*
>> *        A[2] = M[i] + b;*
>> *        A[3] = M[i] + b;*
>> *    }*
>>
>
> ​The transformed code should be
>
>     *int A[4];    *
>
> *    for (int i = 0; i < N; i+=4) {*
> *        A[0] = M[i] + b;*
> *        A[1] = M[i+1] + b;*
> *        A[2] = M[i+2] + b;*
> *        A[3] = M[i+3] + b;*
> *    }*
>
> ​I would suggest you manually rewrite the code, and see if SLP works on
> it. I think doing the transformation in source level would be easier. Or
> you can observe the IR for both side, see if you can think of algorithm
> handling your case.
>
> --
> Wei-Ren Chen (陳韋任)
> Homepage: https://people.cs.nctu.edu.tw/~chenwj
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-- 
Sincerely,
Linchuan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180115/95e409ed/attachment.html>

> On 15 Jan 2018, at 01:36, Linchuan Chen via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Dear all,
>     I'm working on a simple code transformation problem that can be
described as below:
>  
>     for a C++ loop:
> 
>     for (int i = 0; i < N; ++i) {
>         a = M[i] + b;
>     }
> 
In this example, all stores to a except for the last one are dead.  It is
therefore valid to rewrite this as:

if (N > 0)
{
	a = M[N-1] + b;
}

Indeed, LLVM does this transformation already, translating this loop to 

; Load N
  %2 = load i32, i32* @N, align 4, !tbaa !2
; if N > 0
  %3 = icmp sgt i32 %2, 0
  br i1 %3, label %4, label %10

; <label>:4:                                      ; preds = %1
  %5 = add i32 %2, -1
  %6 = sext i32 %5 to i64
  %7 = getelementptr inbounds [42 x i32], [42 x i32]* @M, i64 0, i64 %6
; Load M[N-1]
  %8 = load i32, i32* %7, align 4, !tbaa !2
; Add b to M[N-1]
  %9 = add nsw i32 %8, %0
  br label %10

; <label>:10:                                     ; preds = %4, %1
  %11 = phi i32 [ %9, %4 ], [ undef, %1 ]
; Result is either undef or M[N-1] + b.


>     I want to transform it to:
>     
>     int A[4];    
> 
>     for (int i = 0; i < N; ++i) {
>         A[0] = M[i] + b;
>         A[1] = M[i] + b;
>         A[2] = M[i] + b;
>         A[3] = M[i] + b;
>     }
> 
>    The reason I want to do it is to transform my code to a form that SLP
vectorizer is able to vectorize it.
This transform looks like loop unrolling, and the loop unroller already does it
(and enabling later vectorisation opportunities is one of the main motivations
for bothering with loop unrolling on modern architectures where loop branches
are almost always correctly predicted).
>    I know there are a few approaches for transforming the code, the
simplest being a naive text processor for duplicating the assignment
instructions in the loop, but I don't think it a standard way for code
transformation.
> 
>    I also got to know a few other alternatives: 
> 	• using libTooling to edit the AST
> 	• transform the IR code of the loop, in a PASS, so that the SLP PASS can
consume the resulting IR
>    Does anyone know which alternative is the most used or most standard way
of doing such a transformation work? Thanks!
Doing this transform at the source level is difficult, because you must infer
all of the data flow information that you get for free in SSA form.  Doing this
in SSA form is much easier and that is where the LLVM pipeline does it already.

David