thr3ads.net - llvm dev - [llvm-dev] CodeExtractor buggy? [Nov 2017]

If this information is useful, please help other people find it:
Share via:

Pei Wang via llvm-dev

2017-Nov-29 01:26 UTC

[llvm-dev] CodeExtractor buggy?

Hi All,

 

I’m currently working on a simple task which needs to transform loops into
tail-recursive functions. I found the CodeExtractor class a handy helper to use,
but later encountered a problem.

 

Consider the following CU

 

struct S { int a, b; };

 

int foo(struct S *s, unsigned n) {

  struct S *next = s;

 

  unsigned i;

  for (i = 0; i < n; ++i) {

    if (!s[i].a)

      break;

    next = s + i;

  }

  return next->b;

}

 

clang 5.0 gives the following IR with O1 optimizations

 

%struct.S = type { i32, i32 }

 

; Function Attrs: norecurse nounwind readonly uwtable

define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {

  %3 = icmp eq i32 %1, 0

  br i1 %3, label %16, label %4

 

; <label>:4:                                      ; preds = %2

  br label %7

 

; <label>:5:                                      ; preds = %7

  %6 = icmp ult i32 %15, %1

  br i1 %6, label %7, label %16

 

; <label>:7:                                      ; preds = %4, %5

  %8 = phi i32 [ %15, %5 ], [ 0, %4 ]

  %9 = phi %struct.S* [ %11, %5 ], [ %0, %4 ]

  %10 = zext i32 %8 to i64

  %11 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %10

  %12 = getelementptr inbounds %struct.S, %struct.S* %11, i64 0, i32 0

  %13 = load i32, i32* %12, align 4, !tbaa !2

  %14 = icmp eq i32 %13, 0

  %15 = add i32 %8, 1

  br i1 %14, label %16, label %5

 

; <label>:16:                                     ; preds = %5, %7, %2

  %17 = phi %struct.S* [ %0, %2 ], [ %9, %7 ], [ %11, %5 ]

  %18 = getelementptr inbounds %struct.S, %struct.S* %17, i64 0, i32 1

  %19 = load i32, i32* %18, align 4, !tbaa !7

  ret i32 %19

}

 

Here %17 should be noted, which is a phi with 3 incoming blocks, with two of
them being part of the loop.

 

After using CodeExtractor to extract the loop into a new function, I got

 

%struct.S = type { i32, i32 }

 

; Function Attrs: norecurse nounwind readonly uwtable

define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {

  %.loc1 = alloca %struct.S*

  %.loc = alloca %struct.S*

  %3 = icmp eq i32 %1, 0

  br i1 %3, label %5, label %4

 

; <label>:4:                                      ; preds = %2

  br label %codeRepl

 

codeRepl:                                         ; preds = %4

  call void @foo_(%struct.S* %0, i32 %1, %struct.S** %.loc, %struct.S** %.loc1)

  %.reload = load %struct.S*, %struct.S** %.loc

  %.reload2 = load %struct.S*, %struct.S** %.loc1

  br label %.loopexit

 

.loopexit:                                        ; preds = %codeRepl

  %.ph = phi %struct.S* [ %.reload2, %codeRepl ], [ %.reload, %codeRepl ]

  br label %5

 

; <label>:5:                                      ; preds = %.loopexit, %2

  %6 = phi %struct.S* [ %0, %2 ], [ %.ph, %.loopexit ]

  %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 1

  %8 = load i32, i32* %7, align 4, !tbaa !2

  ret i32 %8

}

 

; Function Attrs: nounwind uwtable

define internal void @foo_(%struct.S*, i32, %struct.S** %.out, %struct.S**
%.out1) #1 {

newFuncRoot:

  br label %2

 

.loopexit.exitStub:                               ; preds = %11, %2

  store %struct.S* %4, %struct.S** %.out

  store %struct.S* %6, %struct.S** %.out1

  ret void

 

; <label>:2:                                      ; preds = %newFuncRoot,
%11

  %3 = phi i32 [ %10, %11 ], [ 0, %newFuncRoot ]

  %4 = phi %struct.S* [ %6, %11 ], [ %0, %newFuncRoot ]

  %5 = zext i32 %3 to i64

  %6 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %5

  %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 0

  %8 = load i32, i32* %7, align 4, !tbaa !7

  %9 = icmp eq i32 %8, 0

  %10 = add i32 %3, 1

  br i1 %9, label %.loopexit.exitStub, label %11

 

; <label>:11:                                     ; preds = %2

  %12 = icmp ult i32 %10, %1

  br i1 %12, label %2, label %.loopexit.exitStub

}

 

Now, because the loop is coalesced into a function, the definition of %.ph
(derived from %17 in the previous version of IR) in .loopexit becomes funny: two
different incoming values for the same incoming block. I was wondering if this
is a bug of CodeExtractor or the extractor makes assumptions about the code to
be extracted which I’m not aware of.

 

Thanks,

Pei Wang

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171128/834f1483/attachment-0001.html>

Bekket McClane via llvm-dev

2017-Nov-29 01:35 UTC

head link

[llvm-dev] CodeExtractor buggy?

Hi,

I didn’t take a detail look on the problem you encountered, but early this
October(5.0 is released in Sep I remembered), I fixed a bug related to exitStub
in CodeExtractor:
https://reviews.llvm.org/rL315041 <https://reviews.llvm.org/rL315041>
In short, I change the behavior of output variable restoring
Hope this helps

Regards,
Min-Yih> Pei Wang via llvm-dev <llvm-dev at lists.llvm.org> 於 2017年11月29日
上午9:26 寫道：
> 
> Hi All,
>  
> I’m currently working on a simple task which needs to transform loops into
tail-recursive functions. I found the CodeExtractor class a handy helper to use,
but later encountered a problem.
>  
> Consider the following CU
>  
> struct S { int a, b; };
>  
> int foo(struct S *s, unsigned n) {
>   struct S *next = s;
>  
>   unsigned i;
>   for (i = 0; i < n; ++i) {
>     if (!s[i].a)
>       break;
>     next = s + i;
>   }
>   return next->b;
> }
>  
> clang 5.0 gives the following IR with O1 optimizations
>  
> %struct.S = type { i32, i32 }
>  
> ; Function Attrs: norecurse nounwind readonly uwtable
> define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {
>   %3 = icmp eq i32 %1, 0
>   br i1 %3, label %16, label %4
>  
> ; <label>:4:                                      ; preds = %2
>   br label %7
>  
> ; <label>:5:                                      ; preds = %7
>   %6 = icmp ult i32 %15, %1
>   br i1 %6, label %7, label %16
>  
> ; <label>:7:                                      ; preds = %4, %5
>   %8 = phi i32 [ %15, %5 ], [ 0, %4 ]
>   %9 = phi %struct.S* [ %11, %5 ], [ %0, %4 ]
>   %10 = zext i32 %8 to i64
>   %11 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %10
>   %12 = getelementptr inbounds %struct.S, %struct.S* %11, i64 0, i32 0
>   %13 = load i32, i32* %12, align 4, !tbaa !2
>   %14 = icmp eq i32 %13, 0
>   %15 = add i32 %8, 1
>   br i1 %14, label %16, label %5
>  
> ; <label>:16:                                     ; preds = %5, %7,
%2
>   %17 = phi %struct.S* [ %0, %2 ], [ %9, %7 ], [ %11, %5 ]
>   %18 = getelementptr inbounds %struct.S, %struct.S* %17, i64 0, i32 1
>   %19 = load i32, i32* %18, align 4, !tbaa !7
>   ret i32 %19
> }
>  
> Here %17 should be noted, which is a phi with 3 incoming blocks, with two
of them being part of the loop.
>  
> After using CodeExtractor to extract the loop into a new function, I got
>  
> %struct.S = type { i32, i32 }
>  
> ; Function Attrs: norecurse nounwind readonly uwtable
> define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {
>   %.loc1 = alloca %struct.S*
>   %.loc = alloca %struct.S*
>   %3 = icmp eq i32 %1, 0
>   br i1 %3, label %5, label %4
>  
> ; <label>:4:                                      ; preds = %2
>   br label %codeRepl
>  
> codeRepl:                                         ; preds = %4
>   call void @foo_(%struct.S* %0, i32 %1, %struct.S** %.loc, %struct.S**
%.loc1)
>   %.reload = load %struct.S*, %struct.S** %.loc
>   %.reload2 = load %struct.S*, %struct.S** %.loc1
>   br label %.loopexit
>  
> .loopexit:                                        ; preds = %codeRepl
>   %.ph = phi %struct.S* [ %.reload2, %codeRepl ], [ %.reload, %codeRepl ]
>   br label %5
>  
> ; <label>:5:                                      ; preds =
%.loopexit, %2
>   %6 = phi %struct.S* [ %0, %2 ], [ %.ph, %.loopexit ]
>   %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 1
>   %8 = load i32, i32* %7, align 4, !tbaa !2
>   ret i32 %8
> }
>  
> ; Function Attrs: nounwind uwtable
> define internal void @foo_(%struct.S*, i32, %struct.S** %.out, %struct.S**
%.out1) #1 {
> newFuncRoot:
>   br label %2
>  
> .loopexit.exitStub:                               ; preds = %11, %2
>   store %struct.S* %4, %struct.S** %.out
>   store %struct.S* %6, %struct.S** %.out1
>   ret void
>  
> ; <label>:2:                                      ; preds =
%newFuncRoot, %11
>   %3 = phi i32 [ %10, %11 ], [ 0, %newFuncRoot ]
>   %4 = phi %struct.S* [ %6, %11 ], [ %0, %newFuncRoot ]
>   %5 = zext i32 %3 to i64
>   %6 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %5
>   %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 0
>   %8 = load i32, i32* %7, align 4, !tbaa !7
>   %9 = icmp eq i32 %8, 0
>   %10 = add i32 %3, 1
>   br i1 %9, label %.loopexit.exitStub, label %11
>  
> ; <label>:11:                                     ; preds = %2
>   %12 = icmp ult i32 %10, %1
>   br i1 %12, label %2, label %.loopexit.exitStub
> }
>  
> Now, because the loop is coalesced into a function, the definition of %.ph
(derived from %17 in the previous version of IR) in .loopexit becomes funny: two
different incoming values for the same incoming block. I was wondering if this
is a bug of CodeExtractor or the extractor makes assumptions about the code to
be extracted which I’m not aware of.
>  
> Thanks,
> Pei Wang
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171129/fc850c9d/attachment.html>

Pei Wang via llvm-dev

2017-Nov-29 16:13 UTC

head link

[llvm-dev] CodeExtractor buggy?

Hi Min-Yih,

 

Thanks for the help. I tried your patch but it didn’t work for my case. I think
my problem is more related to output variable recognition.

 

Pei

 

From: Bekket McClane <bekket.mcclane at gmail.com>
Date: Tuesday, November 28, 2017 at 8:35 PM
To: Pei Wang <uraj.wp at gmail.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] CodeExtractor buggy?

 

Hi,

 

I didn’t take a detail look on the problem you encountered, but early this
October(5.0 is released in Sep I remembered), I fixed a bug related to exitStub
in CodeExtractor:

https://reviews.llvm.org/rL315041

In short, I change the behavior of output variable restoring

Hope this helps

 

Regards,

Min-Yih

Pei Wang via llvm-dev <llvm-dev at lists.llvm.org> 於 2017年11月29日 上午9:26
寫道：

 

Hi All,

 

I’m currently working on a simple task which needs to transform loops into
tail-recursive functions. I found the CodeExtractor class a handy helper to use,
but later encountered a problem.

 

Consider the following CU

 

struct S { int a, b; };

 

int foo(struct S *s, unsigned n) {

  struct S *next = s;

 

  unsigned i;

  for (i = 0; i < n; ++i) {

    if (!s[i].a)

      break;

    next = s + i;

  }

  return next->b;

}

 

clang 5.0 gives the following IR with O1 optimizations

 

%struct.S = type { i32, i32 }

 

; Function Attrs: norecurse nounwind readonly uwtable

define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {

  %3 = icmp eq i32 %1, 0

  br i1 %3, label %16, label %4

 

; <label>:4:                                      ; preds = %2

  br label %7

 

; <label>:5:                                      ; preds = %7

  %6 = icmp ult i32 %15, %1

  br i1 %6, label %7, label %16

 

; <label>:7:                                      ; preds = %4, %5

  %8 = phi i32 [ %15, %5 ], [ 0, %4 ]

  %9 = phi %struct.S* [ %11, %5 ], [ %0, %4 ]

  %10 = zext i32 %8 to i64

  %11 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %10

  %12 = getelementptr inbounds %struct.S, %struct.S* %11, i64 0, i32 0

  %13 = load i32, i32* %12, align 4, !tbaa !2

  %14 = icmp eq i32 %13, 0

  %15 = add i32 %8, 1

  br i1 %14, label %16, label %5

 

; <label>:16:                                     ; preds = %5, %7, %2

  %17 = phi %struct.S* [ %0, %2 ], [ %9, %7 ], [ %11, %5 ]

  %18 = getelementptr inbounds %struct.S, %struct.S* %17, i64 0, i32 1

  %19 = load i32, i32* %18, align 4, !tbaa !7

  ret i32 %19

}

 

Here %17 should be noted, which is a phi with 3 incoming blocks, with two of
them being part of the loop.

 

After using CodeExtractor to extract the loop into a new function, I got

 

%struct.S = type { i32, i32 }

 

; Function Attrs: norecurse nounwind readonly uwtable

define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {

  %.loc1 = alloca %struct.S*

  %.loc = alloca %struct.S*

  %3 = icmp eq i32 %1, 0

  br i1 %3, label %5, label %4

 

; <label>:4:                                      ; preds = %2

  br label %codeRepl

 

codeRepl:                                         ; preds = %4

  call void @foo_(%struct.S* %0, i32 %1, %struct.S** %.loc, %struct.S** %.loc1)

  %.reload = load %struct.S*, %struct.S** %.loc

  %.reload2 = load %struct.S*, %struct.S** %.loc1

  br label %.loopexit

 

.loopexit:                                        ; preds = %codeRepl

  %.ph = phi %struct.S* [ %.reload2, %codeRepl ], [ %.reload, %codeRepl ]

  br label %5

 

; <label>:5:                                      ; preds = %.loopexit, %2

  %6 = phi %struct.S* [ %0, %2 ], [ %.ph, %.loopexit ]

  %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 1

  %8 = load i32, i32* %7, align 4, !tbaa !2

  ret i32 %8

}

 

; Function Attrs: nounwind uwtable

define internal void @foo_(%struct.S*, i32, %struct.S** %.out, %struct.S**
%.out1) #1 {

newFuncRoot:

  br label %2

 

.loopexit.exitStub:                               ; preds = %11, %2

  store %struct.S* %4, %struct.S** %.out

  store %struct.S* %6, %struct.S** %.out1

  ret void

 

; <label>:2:                                      ; preds = %newFuncRoot,
%11

  %3 = phi i32 [ %10, %11 ], [ 0, %newFuncRoot ]

  %4 = phi %struct.S* [ %6, %11 ], [ %0, %newFuncRoot ]

  %5 = zext i32 %3 to i64

  %6 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %5

  %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 0

  %8 = load i32, i32* %7, align 4, !tbaa !7

  %9 = icmp eq i32 %8, 0

  %10 = add i32 %3, 1

  br i1 %9, label %.loopexit.exitStub, label %11

 

; <label>:11:                                     ; preds = %2

  %12 = icmp ult i32 %10, %1

  br i1 %12, label %2, label %.loopexit.exitStub

}

 

Now, because the loop is coalesced into a function, the definition of %.ph
(derived from %17 in the previous version of IR) in .loopexit becomes funny: two
different incoming values for the same incoming block. I was wondering if this
is a bug of CodeExtractor or the extractor makes assumptions about the code to
be extracted which I’m not aware of.

 

Thanks,

Pei Wang

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

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171129/69dc850b/attachment-0001.html>

serge guelton via llvm-dev

2017-Dec-03 17:07 UTC

head link

[llvm-dev] CodeExtractor buggy?

On Tue, Nov 28, 2017 at 08:26:18PM -0500, Pei Wang via llvm-dev
wrote:> Now, because the loop is coalesced into a function, the definition of %.ph
(derived from %17 in the previous version of IR) in .loopexit becomes funny: two
different incoming values for the same incoming block. I was wondering if this
is a bug of CodeExtractor or the extractor makes assumptions about the code to
be extracted which I’m not aware of.
>From my experience, the CodeExtractor is buggy in various corner cases :-/

keita abdoul-kader via llvm-dev

2017-Dec-04 08:38 UTC

head link

[llvm-dev] CodeExtractor buggy?

I second this observation.

On Sun, Dec 3, 2017 at 9:07 AM, serge guelton via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Tue, Nov 28, 2017 at 08:26:18PM -0500, Pei Wang via llvm-dev wrote:
> > Now, because the loop is coalesced into a function, the definition of
> %.ph (derived from %17 in the previous version of IR) in .loopexit becomes
> funny: two different incoming values for the same incoming block. I was
> wondering if this is a bug of CodeExtractor or the extractor makes
> assumptions about the code to be extracted which I’m not aware of.
>
> From my experience, the CodeExtractor is buggy in various corner cases :-/
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171204/40fee40a/attachment.html>

Apparently Analagous Threads

Search for more possibly parallel threads

llvm dev - Nov 2017 - CodeExtractor buggy?

[llvm-dev] CodeExtractor buggy?

[llvm-dev] CodeExtractor buggy?

[llvm-dev] CodeExtractor buggy?

[llvm-dev] CodeExtractor buggy?

[llvm-dev] CodeExtractor buggy?

Apparently Analagous Threads