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

[Jingu Kang via llvm-dev]

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>