thr3ads.net - llvm dev - [llvm-dev] Question about hoisting LoadInst in LICM pass using MemorySSA/AliasAnalysis [Nov 2021]

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

Neil Henning via llvm-dev

2021-Nov-01 09:02 UTC

[llvm-dev] Question about hoisting LoadInst in LICM pass using MemorySSA/AliasAnalysis

Hey JinGu-nim,

Now I've looked at that example - isn't the problem that TBAA isn't
doing
its job here? `unsigned*` should be distinct from `unsigned**` and TBAA
should say that the pointers can't alias?

We don't have TBAA in Burst, so that's why we had to roll our own alias
analysis with our specific characteristics!

Cheers,
-Neil.

On Mon, Nov 1, 2021 at 8:39 AM Jingu Kang <Jingu.Kang at arm.com> wrote:
> Hello Neil-nim,
>
>
>
> Thanks for kind reply.
>
>
>
> I am fixing https://bugs.llvm.org/show_bug.cgi?id=52143. If we can fix
> the case with AliasAnalysis, it would be a fundamental solution. If
> possible, can I ask you how you fixed it like adding a pattern in BasicAA,
> running other existing AA or your own one and etc please? If Neil-nim
> pushes the solution to upstream, it will be best. 😊
>
>
>
> Cheers,
>
> JinGu Kang
>
>
>
> *From:* Neil Henning <neil.henning at unity3d.com>
> *Sent:* 01 November 2021 07:47
> *To:* Jingu Kang <Jingu.Kang at arm.com>
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* Re: [llvm-dev] Question about hoisting LoadInst in LICM pass
> using MemorySSA/AliasAnalysis
>
>
>
> Hey JinGu!
>
>
>
> I don't know the answer to this from a MemorySSA / LICM perspective
(I'm
> not deeply aware of their internals) - but I do remember having to fix this
> exact kind of issue with our Burst HPC# compiler with our own custom alias
> analysis. From our perspective it was safe to assume that any pointer
> deriving from @a couldn't alias with it, and we could make this
> optimization (this was really important in LLVM 6/7 timeframe if I'm
> remembering it right because we had a lot of cases where these kind of
> things would disable vectorization).
>
>
>
> Cheers,
>
> -Neil.
>
>
>
> On Fri, Oct 29, 2021 at 7:27 PM Jingu Kang via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Ping
>
>
>
> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of
*Jingu
> Kang via llvm-dev
> *Sent:* 27 October 2021 15:15
> *To:* llvm-dev at lists.llvm.org
> *Subject:* [llvm-dev] Question about hoisting LoadInst in LICM pass using
> MemorySSA/AliasAnalysis
>
>
>
> Hi All,
>
>
>
> I have a question about hoisting LoadInst in LICM pass. I am looking at
> below IR code.
>
>
>
> @a = dso_local local_unnamed_addr global i32** null, align 8
>
>
>
> define dso_local void @foo(i32 %max) {
>
> entry:
>
>   br label %for.cond
>
>
>
> for.cond:                                         ; preds = %for.body,
> %entry
>
>   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
>
>   %cmp.not = icmp sgt i32 %i.0, %max
>
>   br i1 %cmp.not, label %for.cond.cleanup, label %for.body
>
>
>
> for.cond.cleanup:                                 ; preds = %for.cond
>
>   ret void
>
>
>
> for.body:                                         ; preds = %for.cond
>
>   %0 = load i32**, i32*** @a, align 8, !tbaa !8
>
>   %idxprom = zext i32 %i.0 to i64
>
>   %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
>
>   store i32* null, i32** %arrayidx, align 8, !tbaa !8
>
>   %inc = add nuw nsw i32 %i.0, 1
>
>   br label %for.cond, !llvm.loop !12
>
> }
>
>
>
> I have expected the `%0 = load` is hoisted to entry block because I think
> it is loop invariant. However, LICM pass fails to hoist it because the
> MemorySSA is as below.
>
>
>
> define dso_local void @foo(i32 %max) local_unnamed_addr #0 {
>
> entry:
>
>   br label %for.cond
>
>
>
> for.cond:                                         ; preds = %for.body,
> %entry
>
> ; 2 = MemoryPhi({entry,liveOnEntry},{for.body,1})
>
>   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
>
>   %cmp.not = icmp sgt i32 %i.0, %max
>
>   br i1 %cmp.not, label %for.cond.cleanup, label %for.body
>
>
>
> for.cond.cleanup:                                 ; preds = %for.cond
>
>   ret void
>
>
>
> for.body:                                         ; preds = %for.cond
>
> ; MemoryUse(2) MayAlias
>
>   %0 = load i32**, i32*** @a, align 8, !tbaa !8
>
>   %idxprom = zext i32 %i.0 to i64
>
>   %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
>
> ; 1 = MemoryDef(2)
>
>   store i32* null, i32** %arrayidx, align 8, !tbaa !8
>
>   %inc = add nuw nsw i32 %i.0, 1
>
>   br label %for.cond, !llvm.loop !12
>
> }
>
>
>
> As we can see there is `MemoryUse(2) MayAlias` above the `%0 = load`
> because AliasAnalysis returns MayAlias between the ‘%0 = load’ and ‘store
> i32* null’. I think it could be `MemoryUse(liveOnEntry)`. How do you think
> about it? If I missed something, please let me know.
>
>
>
> Thanks,
>
> JinGu Kang
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> --
>
> [image: Image removed by sender.]
>
> *Neil Henning*
>
> Senior Software Engineer Compiler
>
> unity.com
>
>
>

-- 
Neil Henning
Senior Software Engineer Compiler
unity.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211101/0808987b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ~WRD0000.jpg
Type: image/jpeg
Size: 823 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211101/0808987b/attachment.jpg>

Jingu Kang via llvm-dev

2021-Nov-01 11:36 UTC

head link

[llvm-dev] Question about hoisting LoadInst in LICM pass using MemorySSA/AliasAnalysis

Neil-nim,

The load and store have same TBAA MDNode so the TBAA returns MayAlias. I am not
sure we can solve this case on the TBAA…

As we can see on the IR example, the load and store have WAR dependency at the
first iteration of the loop and there is no dependency at rest of iterations of
the loop. I think it could be good to check this information somewhere to hoist
the load.

Thanks
JinGu Kang

From: Neil Henning <neil.henning at unity3d.com>
Sent: 01 November 2021 09:02
To: Jingu Kang <Jingu.Kang at arm.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Question about hoisting LoadInst in LICM pass using
MemorySSA/AliasAnalysis

Hey JinGu-nim,

Now I've looked at that example - isn't the problem that TBAA isn't
doing its job here? `unsigned*` should be distinct from `unsigned**` and TBAA
should say that the pointers can't alias?

We don't have TBAA in Burst, so that's why we had to roll our own alias
analysis with our specific characteristics!

Cheers,
-Neil.

On Mon, Nov 1, 2021 at 8:39 AM Jingu Kang <Jingu.Kang at
arm.com<mailto:Jingu.Kang at arm.com>> wrote:
Hello Neil-nim,

Thanks for kind reply.

I am fixing https://bugs.llvm.org/show_bug.cgi?id=52143. If we can fix the case
with AliasAnalysis, it would be a fundamental solution. If possible, can I ask
you how you fixed it like adding a pattern in BasicAA, running other existing AA
or your own one and etc please? If Neil-nim pushes the solution to upstream, it
will be best. 😊

Cheers,
JinGu Kang

From: Neil Henning <neil.henning at unity3d.com<mailto:neil.henning at
unity3d.com>>
Sent: 01 November 2021 07:47
To: Jingu Kang <Jingu.Kang at arm.com<mailto:Jingu.Kang at arm.com>>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Question about hoisting LoadInst in LICM pass using
MemorySSA/AliasAnalysis

Hey JinGu!

I don't know the answer to this from a MemorySSA / LICM perspective (I'm
not deeply aware of their internals) - but I do remember having to fix this
exact kind of issue with our Burst HPC# compiler with our own custom alias
analysis. From our perspective it was safe to assume that any pointer deriving
from @a couldn't alias with it, and we could make this optimization (this
was really important in LLVM 6/7 timeframe if I'm remembering it right
because we had a lot of cases where these kind of things would disable
vectorization).

Cheers,
-Neil.

On Fri, Oct 29, 2021 at 7:27 PM Jingu Kang via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Ping

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> On Behalf Of Jingu Kang via llvm-dev
Sent: 27 October 2021 15:15
To: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: [llvm-dev] Question about hoisting LoadInst in LICM pass using
MemorySSA/AliasAnalysis

Hi All,

I have a question about hoisting LoadInst in LICM pass. I am looking at below IR
code.

@a = dso_local local_unnamed_addr global i32** null, align 8

define dso_local void @foo(i32 %max) {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.body, %entry
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %cmp.not = icmp sgt i32 %i.0, %max
  br i1 %cmp.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:                                 ; preds = %for.cond
  ret void

for.body:                                         ; preds = %for.cond
  %0 = load i32**, i32*** @a, align 8, !tbaa !8
  %idxprom = zext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
  store i32* null, i32** %arrayidx, align 8, !tbaa !8
  %inc = add nuw nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !12
}

I have expected the `%0 = load` is hoisted to entry block because I think it is
loop invariant. However, LICM pass fails to hoist it because the MemorySSA is as
below.

define dso_local void @foo(i32 %max) local_unnamed_addr #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.body, %entry
; 2 = MemoryPhi({entry,liveOnEntry},{for.body,1})
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %cmp.not = icmp sgt i32 %i.0, %max
  br i1 %cmp.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:                                 ; preds = %for.cond
  ret void

for.body:                                         ; preds = %for.cond
; MemoryUse(2) MayAlias
  %0 = load i32**, i32*** @a, align 8, !tbaa !8
  %idxprom = zext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
; 1 = MemoryDef(2)
  store i32* null, i32** %arrayidx, align 8, !tbaa !8
  %inc = add nuw nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !12
}

As we can see there is `MemoryUse(2) MayAlias` above the `%0 = load` because
AliasAnalysis returns MayAlias between the ‘%0 = load’ and ‘store i32* null’. I
think it could be `MemoryUse(liveOnEntry)`. How do you think about it? If I
missed something, please let me know.

Thanks,
JinGu Kang
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
[Image removed by sender.]
Neil Henning
Senior Software Engineer Compiler
unity.com<http://unity.com>



--
[Image removed by sender.]
Neil Henning
Senior Software Engineer Compiler
unity.com<http://unity.com>

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211101/4acf506e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 823 bytes
Desc: image001.jpg
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211101/4acf506e/attachment.jpg>

llvm dev - Nov 2021 - Question about hoisting LoadInst in LICM pass using MemorySSA/AliasAnalysis

[llvm-dev] Question about hoisting LoadInst in LICM pass using MemorySSA/AliasAnalysis

[llvm-dev] Question about hoisting LoadInst in LICM pass using MemorySSA/AliasAnalysis