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!

​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.

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!!

What I mean is, I would modify the code manually and see if SLP works on
it. If so, we know what code
​ we have to output in the end, and

​this is​
the first step. Then
​to
know if the transformation can be done in source or IR level.
​You can compare the IR ​
before and after the
​ modification
​ to know if IR transformation can be done easily or not. If it's easy,
then write a IR transformation; otherwise, you can do source transformation
by using LibTooling [1]. Asking question about
LibTooling
​ on cfe-dev [2] would be appropriate.

[1]
https://clang.llvm.org/docs/LibTooling.html​
​[2] https://lists.llvm.org/mailman/listinfo/cfe-dev​

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