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 07:47 UTC

[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
>

-- 
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/75236c23/attachment.html>

Jingu Kang via llvm-dev

2021-Nov-01 08:39 UTC

head link

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

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<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>

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211101/4359620f/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ~WRD0000.jpg
Type: image/jpeg
Size: 823 bytes
Desc: ~WRD0000.jpg
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211101/4359620f/attachment-0001.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