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

Mon Nov 1 04:36:40 PDT 2021

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>