[llvm-dev] CodeExtractor buggy?

Wed Nov 29 08:13:18 PST 2017

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>