[llvm-dev] Question about supporting zext on IVUsers and LSR

5 views
Skip to first unread message

Jingu Kang via llvm-dev

unread,
Nov 25, 2021, 9:38:08 AM11/25/21
to llvm...@lists.llvm.org

Hi All,

 

I am looking at a simple example as below.

 

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"

target triple = "aarch64-unknown-linux-gnu"

 

%struct.base_s = type { %struct.range, i64, i64, i64*, i32, [4 x i32], [274 x %struct.match], i32, i32, i8, i8, i8, i32, i32, i32, [16 x [768 x i16]], [12 x [16 x i16]], [12 x i16], [12 x i16], [12 x i16], [12 x i16], [12 x [16 x i16]], [4 x [64 x i16]], [114 x i16], [16 x i16], %struct.length, %struct.length, [4 x [64 x i32]], [4 x [128 x i32]], i32, i32, [16 x i32], i32, i32, i32, [4096 x %struct.opt] }

%struct.range = type { i64, i64, i32, i8, i64, i32, i32, [53 x i32], [53 x i16*] }

%struct.match = type { i32, i32 }

%struct.length = type { i16, i16, [16 x [8 x i16]], [16 x [8 x i16]], [256 x i16], [16 x [272 x i32]], i32, [16 x i32] }

%struct.opt = type { i32, i8, i8, i32, i32, i32, i32, i32, [4 x i32] }

 

define i32 @test(i32 %len, %struct.base_s* nocapture readonly %obj) {

entry:

  br label %while.cond

 

while.cond:                                       ; preds = %while.cond, %entry

  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]

  %idxprom = zext i32 %i.0 to i64

  %len1 = getelementptr inbounds %struct.base_s, %struct.base_s* %obj, i64 0, i32 6, i64 %idxprom, i32 0

  %0 = load i32, i32* %len1, align 4

  %cmp = icmp ult i32 %0, %len

  %inc = add i32 %i.0, 1

  br i1 %cmp, label %while.cond, label %while.end

 

while.end:                                        ; preds = %while.cond

  ret i32 %i.0

}

 

I expected the LSR pass extracts the loop invariant part from `%len1 = getelementptr` and hoists it to preheader. It could cause a new IV for the loop dependent part from gep inside loop and `%0 = load` could use it. However, it looks the `IVUsers` does process the `%idxprom = zext`. I can see the `SCEVAddRecExpr` and `SCEVAddExpr` are handled in `isInteresting` function. It seems LSR pass does not also handle the `zext` for `IVChain`. If I remove the `%idxprom = zext` manually on above example, I can see LSR works as the expectation. Does anyone know why the `zext` is not supported on IVUsers and LSR? Does it make LSR difficult to construct formulas and compare them?  If I missed something, please let me know.

 

For reference, the assembly output of above example with `-O3` is as below.

 

test:

               mov       w8, w0

               mov       w0, #-1

.LBB0_1:

               add        w0, w0, #1

               add        x9, x1, w0, uxtw #3

               ldr          w9, [x9, #724]

               cmp       w9, w8

               b.lo        .LBB0_1

               Ret

 

If I remove the `zext`, the output is as below and the loop has one less instruction against above output.

 

test:

               add        x9, x1, #724

               mov       x8, #-1

.LBB0_1:

               ldr          w10, [x9], #8

               add        x8, x8, #1

               cmp       w10, w0

               b.lo        .LBB0_1

               mov       x0, x8

               ret

 

The IR code, in which the `zext` is removed, is as below.

 

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"

target triple = "aarch64-unknown-linux-gnu"

 

%struct.base_s = type { %struct.range, i64, i64, i64*, i32, [4 x i32], [274 x %struct.match], i32, i32, i8, i8, i8, i32, i32, i32, [16 x [768 x i16]], [12 x [16 x i16]], [12 x i16], [12 x i16], [12 x i16], [12 x i16], [12 x [16 x i16]], [4 x [64 x i16]], [114 x i16], [16 x i16], %struct.length, %struct.length, [4 x [64 x i32]], [4 x [128 x i32]], i32, i32, [16 x i32], i32, i32, i32, [4096 x %struct.opt] }

%struct.range = type { i64, i64, i32, i8, i64, i32, i32, [53 x i32], [53 x i16*] }

%struct.match = type { i32, i32 }

%struct.length = type { i16, i16, [16 x [8 x i16]], [16 x [8 x i16]], [256 x i16], [16 x [272 x i32]], i32, [16 x i32] }

%struct.opt = type { i32, i8, i8, i32, i32, i32, i32, i32, [4 x i32] }

 

;define i32 @test(i32 %len, %struct.base_s* nocapture readonly %obj) {

define i64 @test(i32 %len, %struct.base_s* nocapture readonly %obj) {

entry:

  br label %while.cond

 

while.cond:                                       ; preds = %while.cond, %entry

;  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]

  %i.0 = phi i64 [ 0, %entry ], [ %inc, %while.cond ]

;  %idxprom = zext i32 %i.0 to i64

;  %len1 = getelementptr inbounds %struct.base_s, %struct.base_s* %obj, i64 0, i32 6, i64 %idxprom, i32 0

  %len1 = getelementptr inbounds %struct.base_s, %struct.base_s* %obj, i64 0, i32 6, i64 %i.0, i32 0

  %0 = load i32, i32* %len1, align 4

  %cmp = icmp ult i32 %0, %len

;  %inc = add i32 %i.0, 1

  %inc = add i64 %i.0, 1

  br i1 %cmp, label %while.cond, label %while.end

 

while.end:                                        ; preds = %while.cond

;  ret i32 %i.0

  ret i64 %i.0

}

 

Thanks

JinGu Kang

Philip Reames via llvm-dev

unread,
Nov 29, 2021, 12:57:44 PM11/29/21
to Jingu Kang, llvm...@lists.llvm.org

First, there are no "simple" question about LSR.  :)

Second, I wouldn't view your example as an LSR problem, but a failed IR canonicalization.  In the example, we'd try to widen the IV in IndVars, and LSR would expect the widening to have already been done.  I'd take a look into why we're not widening the IV as your next step.

Philip

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Jingu Kang via llvm-dev

unread,
Dec 1, 2021, 6:00:44 AM12/1/21
to Philip Reames, llvm...@lists.llvm.org

Hi Philip,

 

I appreciate your kind guide.

 

As you mentioned, the IndVars tries to widen the IV from the example. The SCEV fails to generate AddRecExpr from the zext because there could be overflow in `%inc = add i32 %i.0, 1`.

 

Let me check why clang does not set the NUW flag to `%inc = add i32 %i.0, 1`.

 

Thanks,

JinGu Kang

Reply all
Reply to author
Forward
0 new messages