[llvm-dev] Question about supporting zext on IVUsers and LSR
Jingu Kang via llvm-dev
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
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
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