[llvm-dev] gep and strength reduction

[Alexandre Isoard via llvm-dev]

Hello,

I was wondering if we had a way to strength reduce getelementptr today.

For the following code:

void func(float (&A)[132][140]) {
>   for (int i = 0; i < 132; ++i)
>     for (int j = 0; j < 140; ++j)
>       A[i][j] += 1;
> }


We will generate: (annotated with SCEV)

define void @func([132 x [140 x float]]* nocapture dereferenceable(73920))
local_unnamed_addr #0 {
  br label %2

; <label>:2:                                      ; preds = %11, %1
; loop<%2> at depth 1 with exact backedge-taken count of 131
; %12 = {1,+,1}<nuw><nsw><%2>
; %3 = {0,+,1}<nuw><nsw><%2>
  %3 = phi i64 [ 0, %1 ], [ %12, %11 ]
  br label %4

; <label>:4:                                      ; preds = %4, %2
; loop<%4> at depth 2 with exact backedge-taken count of 139
; %5 = {0,+,1}<nuw><nsw><%4>
  %5 = phi i64 [ 0, %2 ], [ %9, %4 ]
; %3 = {0,+,1}<nuw><nsw><%2>
; %6 = {{%0,+,560}<nsw><%2>,+,4}<nw><%4>
  %6 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]*
%0, i64 0, *i64 %3, i64 %5*
  %7 = load float, float* %6, align 4, !tbaa !2
  %8 = fadd float %7, 1.000000e+00
  store float %8, float* %6, align 4, !tbaa !2
; %9 = {1,+,1}<nuw><nsw><%4>
  %9 = add nuw nsw i64 %5, 1
  %10 = icmp eq i64 %9, 140
  br i1 %10, label %11, label %4

; <label>:11:                                     ; preds = %4
; loop<%2> at depth 1 with exact backedge-taken count of 131
; %3 = {0,+,1}<nuw><nsw><%2>
; %12 = {1,+,1}<nuw><nsw><%2>
  %12 = add nuw nsw i64 %3, 1
  %13 = icmp eq i64 %12, 132
  br i1 %13, label %14, label %2

; <label>:14:                                     ; preds = %11
  ret void
}

And we see clearly that the gep is "complicated" in the sense that it does
two addition and two multiplication.

Instead we could produce the following code:

define void @func([132 x [140 x float]]* nocapture dereferenceable(73920))
local_unnamed_addr #0 {
  br label %2

; <label>:2:                                      ; preds = %12, %1
; loop<%2> at depth 1 with exact backedge-taken count of 131
; %13 = {1,+,1}<nuw><nsw><%2>
; %3 = {0,+,1}<nuw><nsw><%2>
  %3 = phi i64 [ 0, %1 ], [ %13, %12 ]
; %4 = {%0,+,560}<nsw><%2>
  %4 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]*
%0, i64 0, *i64 %3*
  br label %5

; <label>:5:                                      ; preds = %5, %2
; loop<%5> at depth 2 with exact backedge-taken count of 139
; %6 = {0,+,1}<nuw><nsw><%5>
  %6 = phi i64 [ 0, %2 ], [ %10, %5 ]
; %4 = {%0,+,560}<nsw><%2>
; %7 = {{%0,+,560}<nsw><%2>,+,4}<nsw><%5>
  %7 = getelementptr inbounds [140 x float], [140 x float]* %4, i64 0, *i64
%6*
  %8 = load float, float* %7, align 4, !tbaa !2
  %9 = fadd float %8, 1.000000e+00
  store float %9, float* %7, align 4, !tbaa !2
; %10 = {1,+,1}<nuw><nsw><%5>
  %10 = add nuw nsw i64 %6, 1
  %11 = icmp eq i64 %10, 140
  br i1 %11, label %12, label %5

; <label>:12:                                     ; preds = %5
; loop<%2> at depth 1 with exact backedge-taken count of 131
; %3 = {0,+,1}<nuw><nsw><%2>
; %13 = {1,+,1}<nuw><nsw><%2>
  %13 = add nuw nsw i64 %3, 1
  %14 = icmp eq i64 %13, 132
  br i1 %14, label %15, label %2

; <label>:15:                                     ; preds = %12
  ret void
}

Where the gep has been strength reduced to one addition one multiplication.

Or even better (at least on the architecture I'm targeting):

define void @func([132 x [140 x float]]* nocapture dereferenceable(73920))
local_unnamed_addr #0 {
; %2 = %0
  %2 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]*
%0, i64 0, i64 0
; %3 = (73920 + %0)<nsw>
  %3 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]*
%0, i64 1, i64 0
  br label %4

; <label>:4:                                      ; preds = %14, %1
; loop<%4> at depth 1 with exact backedge-taken count of 131
; %2 = %0
; %15 = {(560 + %0)<nsw>,+,560}<nuw><%4>
; %5 = {%0,+,560}<nuw><%4>
  %5 = phi [140 x float]* [ %2, %1 ], [ %15, %14 ]
; %6 = {%0,+,560}<nuw><%4>
  %6 = getelementptr inbounds [140 x float], [140 x float]* %5, i64 0, i64 0
; %7 = {(560 + %0)<nsw>,+,560}<nuw><%4>
  %7 = getelementptr inbounds [140 x float], [140 x float]* %5, i64 1, i64 0
  br label %8

; <label>:8:                                      ; preds = %8, %4
; loop<%8> at depth 2 with exact backedge-taken count of 139
; %6 = {%0,+,560}<nuw><%4>
; %9 = {{%0,+,560}<nuw><%4>,+,4}<nuw><%8>
  %9 = phi float* [ %6, %4 ], [ %12, %8 ]
  %10 = load float, float* %9, align 4, !tbaa !2
  %11 = fadd float %10, 1.000000e+00
  store float %11, float* %9, align 4, !tbaa !2
; %12 = {{(4 + %0)<nsw>,+,560}<nw><%4>,+,4}<nuw><%8>
  %12 = getelementptr inbounds float, float* %9, i64 1
; %7 = {(560 + %0)<nsw>,+,560}<nuw><%4>
  %13 = icmp eq float* %12, %7
  br i1 %13, label %14, label %8

; <label>:14:                                     ; preds = %8
; loop<%4> at depth 1 with exact backedge-taken count of 131
; %5 = {%0,+,560}<nuw><%4>
; %15 = {(560 + %0)<nsw>,+,560}<nuw><%4>
  %15 = getelementptr inbounds [140 x float], [140 x float]* %5, i64 1
; %3 = (73920 + %0)<nsw>
  %16 = icmp eq [140 x float]* %15, %3
  br i1 %16, label %17, label %4

; <label>:17:                                     ; preds = %14
  ret void
}

Where we only have addition by a constant (I also got rid of the induction
variables, but that's just being fancy). Do we have a way to do that
automatically?

Why don't we? (I'm guessing because that's negligible on X86)

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180524/99e18f21/attachment.html>