[llvm-dev] Source level code transformation V.S. IR-level code transformation

[David Chisnall via llvm-dev]

> 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