This is an archive of the discontinued LLVM Phabricator instance.

[LICM] Support sinking in LNICM
ClosedPublic

Authored by uint256_t on Jul 31 2021, 3:50 AM.

Details

Summary

Currently, LNICM pass does not support sinking instructions out of loop nest.
This patch enables LNICM to sink down as many instructions to the exit block of outermost loop as possible.

Diff Detail

Event Timeline

uint256_t created this revision.Jul 31 2021, 3:50 AM
uint256_t requested review of this revision.Jul 31 2021, 3:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 31 2021, 3:50 AM
xbolva00 added inline comments.
llvm/test/Transforms/LICM/lnicm-sink.ll
12

j not used? It would be better to use more “realistic” example.

uint256_t added inline comments.Jul 31 2021, 5:29 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
12

I don't think j need to be used. This test shows how LNICM handles a loop nest when it does sinking. If we use j here, an instruction using it would be neither hoisted or sunk, so I think it is redundant.

uint256_t updated this revision to Diff 363290.Jul 31 2021, 5:32 AM

Updated test to make it more readable

uint256_t updated this revision to Diff 364053.Aug 4 2021, 4:52 AM

Fixed bug

uint256_t updated this revision to Diff 364076.Aug 4 2021, 5:55 AM

Fixed test

Whitney added inline comments.Aug 4 2021, 6:35 AM
llvm/include/llvm/Transforms/Utils/LoopUtils.h
157

Please add description for this function.

llvm/test/Transforms/LICM/lnicm-sink.ll
16

Why y[i] = s; is needed for this test case?

uint256_t added inline comments.Aug 4 2021, 6:41 AM
llvm/include/llvm/Transforms/Utils/LoopUtils.h
157

Ok, I'll add a brief description.

llvm/test/Transforms/LICM/lnicm-sink.ll
16

It is to show that LNICM maintains perfect loop nest.
LICM sinks s = abs(i); to right before y[i] = s;, whereas LNICM doesn't do so.

Whitney added inline comments.Aug 4 2021, 7:17 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
16

Why wouldn't LICM sink s = abs(i); without y[i] = s;?

uint256_t added inline comments.Aug 4 2021, 7:24 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
16

LICM would hoist (not sink) s = abs(i); out of loop-j.

Whitney added inline comments.Aug 4 2021, 7:53 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
16

how about

;   for (int i = 0; i < 10; i++) {
;     for (int j = 0; j < 10; j++) {
;       t = sin(x);
;       s = abs(i);
;     }
;   }
;  return t + s;

?

uint256_t added inline comments.Aug 4 2021, 8:10 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
16

Oh, it is way better. I'll edit this test case. Thank you.

uint256_t added inline comments.Aug 4 2021, 9:09 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
16

how about

;   for (int i = 0; i < 10; i++) {
;     for (int j = 0; j < 10; j++) {
;       t = sin(x);
;       s = abs(i);
;     }
;   }
;  return t + s;

?

I ran the test case you suggested above, but LICM didn't do what we want...
LICM transformed it into something like this:

;  int i, j;
;  for (i = 0; i < 10; i++) {
;    for (j = 0; j < 10; j++) {
;    }
;  }
;  t = sin(x);
;  s = abs(i);
;  return t + s;

I should make another better test case.

Whitney added inline comments.Aug 4 2021, 10:47 AM
llvm/test/Transforms/LICM/lnicm-sink.ll
16

I now see the point of y[i] = s;, let's see if you can make a better test case, if not, this is ok with me.

uint256_t updated this revision to Diff 364458.Aug 5 2021, 7:19 AM

Added doc comment

Whitney accepted this revision.Aug 7 2021, 12:18 PM
This revision is now accepted and ready to land.Aug 7 2021, 12:18 PM
bmahjour added inline comments.Aug 9 2021, 9:17 AM
llvm/include/llvm/Transforms/Utils/LoopUtils.h
155

Please name the parameters of this function and add a comment about what each parameter means. Someone reading this declaration and its comments will see two Loop * being passed and cannot figure out what they are without going through its implementation.

uint256_t added inline comments.Aug 9 2021, 7:51 PM
llvm/include/llvm/Transforms/Utils/LoopUtils.h
155

Okay, I'll name the parameter Loop * = nullptr and add a comment to explain what two Loop * are. I don't think I need to name all parameters.

uint256_t updated this revision to Diff 365344.Aug 9 2021, 8:51 PM

Added doc comment

Hi,

The following starts failing with this patch:

opt -passes='loop-mssa(lnicm)' -o /dev/null lnicm-crash.ll

I get

While deleting: i40 %
Use still stuck around after Def is destroyed:  %v_299.017 = phi i40 [ <badref>, %for.body1143 ]
opt: ../lib/IR/Value.cpp:103: llvm::Value::~Value(): Assertion `materialized_use_empty() && "Uses remain when a value is destroyed!"' failed.

Thank you for the report. I'll look into it.

fhahn added a subscriber: fhahn.Dec 14 2021, 3:57 AM

It looks like @uabelho may found another crash in sinkRegionForLoopNest https://github.com/llvm/llvm-project/issues/52688. Please take a look.

Thank you for your report. I'm investigating the problem and making a patch for it.