[LICM] - Add option to force thread model single

[gsocshubham]

Summary

Load is hoisted out of loop while store is sinked if -

a. ThreadModelSingle is set using flag -licm-force-thread-model-single
b. Thread Model is set Single from Clang

This patch resolves - https://github.com/llvm/llvm-project/issues/50537.

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

1856

Removed.

2115

I am not sure about writing to a constant. Can you elaborate with an example where it would fail?

llvm/test/Transforms/LICM/reg-promote.ll

18

I used mem2reg to remove allocas from test but it changes the state of program which will prohibit the optimization which I am proposing.

188

Removed.

[efriedma]

Can we make this work off the existing clang option -mthread-model=single?

[gsocshubham]

Use ThreadModel::Single instead of custom flag.

[gsocshubham]

In D130466#3694507, @efriedma wrote:

Can we make this work off the existing clang option -mthread-model=single?

Done.

I have removed the flag. Now, if ThreadModel::Single is set, LICM will hoist load.

[fhahn]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

This doesn't like quite right. You are just comparing the enum value, not the actual configured ThreadModel I think. You likely have to check the value returned by getThreadModel.

[xbolva00]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

and no tests?

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

getThreadModel() is declared here - https://github.com/llvm/llvm-project/blob/d0541b47000739c68c540170c6b9790ec1ea3b77/llvm/include/llvm/CodeGen/CommandFlags.h#L42

Defination is present in clang - https://github.com/llvm/llvm-project/blob/448adfee05b737a26dda34e7ae2cd4948760fff0/clang/include/clang/Driver/ToolChain.h#L573

virtual std::string getThreadModel() const { return "posix"; }

I am not sure on how can I use getThreadModel() in LICM.cpp. Is there any other way to know ThreadModel?

2115

I have added a test here - hoist-load-without-store.ll where load is hoisted out of loop.

I did not get what do you mean by no tests?

[xbolva00]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

So maybe clang can run llvm with

-mllvm -your-new-flag-to-allow-data-races

if threadmodel is single?

[xbolva00]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

Tests that we perform this optimization only when threadmodel is single

[hiraditya]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

Yeah, we need test checks the optimization was performed when threadmodel is single, and does not do the optimization otherwise.

[gsocshubham]

In D130466#3694507, @efriedma wrote:

Can we make this work off the existing clang option -mthread-model=single?

-mthread-model single does not work for aarch64, sparc and I get below error without any change in the code -

clang-15: error: invalid thread model 'single' in '-mthread-model single' for this target

Target: aarch64-unknown-linux-gnueabihf
Thread model: posix

1. Since, mthread-model single is not supported for most of the architecture, can we keep AllowDataRaces as a separate flag independant from mthread-model?

[gsocshubham]

I have compiled below testcase with options -

../install-aarch64/bin/clang -mthread-model single thread.cpp -S -Ofast
clang-15: error: invalid thread model 'single' in '-mthread-model single' for this target

-------thread.cpp----------

int u, v, restrict, i;

void f(int a[restrict], int b[restrict], int n) {
    for (i = 0; i < n; ++i) {
        if (a[i]) {
            ++u;
            break;
        }
        ++u;
        if (b[i])
            ++v;
    }
}

---

Also, I tried with SPARC -

../install-sparc/bin/clang -mthread-model single thread.cpp -S -Ofast
clang-15: error: invalid thread model 'single' in '-mthread-model single' for this target

while for thread model posix, above commands works fine.

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

1. Passing -mllvm -your-new-flag-to-allow-data-races to clang will work with my original submission - in which there is a new flag AllowDataRaces in LICM.

2. I have tried an approach to let LICM know whether thread model is single or not as below -

a. In clang/lib/CodeGen/BackendUtil.cpp, we have thread model info using LangOpts.getThreadModel()

b. I pass a bool variable to PassBuilder which in turns pass to LICM.

c. LICM based on this bool variable knows whether to hoist the load from the loop if thread model is single or not. I did a trail approach by referring to AllowSpeculation variable which is being passes to LICM. I don't think it is optimal/suggested solution.

From my other comment, first I want to get clear with -mthread-model single option. Can you you comments on it?

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

If we pass thread model information as above, then we don't need flag AllowDataRaces at all. But I think there should be more efficient way apart from above - on how clang driver pass information to llvm passes.

[gsocshubham]

@greened - Can you give suggestions on above comments?

[hiraditya]

In D130466#3709163, @gsocshubham wrote:

I have compiled below testcase with options -

../install-aarch64/bin/clang -mthread-model single thread.cpp -S -Ofast
clang-15: error: invalid thread model 'single' in '-mthread-model single' for this target

-------thread.cpp----------

int u, v, restrict, i;

void f(int a[restrict], int b[restrict], int n) {
    for (i = 0; i < n; ++i) {
        if (a[i]) {
            ++u;
            break;
        }
        ++u;
        if (b[i])
            ++v;
    }
}

---

Also, I tried with SPARC -

../install-sparc/bin/clang -mthread-model single thread.cpp -S -Ofast
clang-15: error: invalid thread model 'single' in '-mthread-model single' for this target

while for thread model posix, above commands works fine.

Check for examples here: test/Driver/thread-model.c

And list of architectures supporting single thread model in https://clang.llvm.org/doxygen/ToolChain_8cpp_source.html#l00729

[gsocshubham]

Fix review comments

1. Updated patch with updated test LICM/promote-sink-store.ll - shows load hoisting and store sinking if flag is set.

2. Added a test LICM/without-allow-data-race.ll which prohibits load hoisting and store sinking if the flag is not set.

3. AllowDataRaces flag can be passed directly to clang -

../install/bin/clang -Ofast -S -promote-sink-store.ll emit-llvm -target aarch64-linux -mllvm -allow-data-races

where IR is obtained from below C testcase -

int u, v;

void f(int a[restrict], int b[restrict], int n) {
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            ++u;
            break;
        }
        ++u;
        if (b[i])
            ++v;
    }
}

TODO -

1. Remove flag -allow-data-races but how feasible it would be to pass thread model information from clang to LICM pass via PassBuilder?

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

2115

@hiraditya - I have added test LICM/without-allow-data-race.ll which shows that optimization is not done when flag is not set - just for confirmation purpose.

I think that it will be redundant test compared to LICM/promote-sink-store.ll and I should probably remove it once patch is ready to commit.

[gsocshubham]

Sink store if architecture supports thread model single.

1. If thread model single is set, then store is sinked.
2. For those architecture which do not support -mthread-model single, they could make use of command line argument -thread-model-single

Let me know suggestions on whether to keep (2) approach or not.

[gsocshubham]

Now for arm-linux when compiled with -Ofast -

int u, v;

void f(int a[restrict], int b[restrict], int n) {
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            ++u;
            break;
        }
        ++u;
        if (b[i])
            ++v;
    }
}

we get -

target triple = "armv4t-unknown-linux"

@u = dso_local local_unnamed_addr global i32 0, align 4
@v = dso_local local_unnamed_addr global i32 0, align 4

; Function Attrs: nofree norecurse nosync nounwind
define dso_local arm_aapcscc void @f(ptr noalias nocapture noundef readonly %0, ptr noalias nocapture noundef readonly %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = load i32, ptr @u, align 4, !tbaa !5
  %5 = load i32, ptr @v, align 4, !tbaa !5
  %6 = icmp sgt i32 %2, 0
  br i1 %6, label %7, label %27

7:                                                ; preds = %3
  %8 = add i32 %4, %2
  br label %9

9:                                                ; preds = %7, %18
  %10 = phi i32 [ %25, %18 ], [ 0, %7 ]
  %11 = phi i32 [ %19, %18 ], [ %4, %7 ]
  %12 = phi i32 [ %24, %18 ], [ %5, %7 ]
  %13 = getelementptr inbounds i32, ptr %0, i32 %10
  %14 = load i32, ptr %13, align 4, !tbaa !5
  %15 = icmp eq i32 %14, 0
  br i1 %15, label %18, label %16

16:                                               ; preds = %9
  store i32 %12, ptr @v, align 4, !tbaa !5
  %17 = add nsw i32 %11, 1
  store i32 %17, ptr @u, align 4, !tbaa !5
  br label %30

18:                                               ; preds = %9
  %19 = add nsw i32 %11, 1
  %20 = getelementptr inbounds i32, ptr %1, i32 %10
  %21 = load i32, ptr %20, align 4, !tbaa !5
  %22 = icmp ne i32 %21, 0
  %23 = zext i1 %22 to i32
  %24 = add nsw i32 %12, %23
  %25 = add nuw nsw i32 %10, 1
  %26 = icmp eq i32 %25, %2
  br i1 %26, label %27, label %9, !llvm.loop !9

27:                                               ; preds = %18, %3
  %28 = phi i32 [ %5, %3 ], [ %24, %18 ]
  %29 = phi i32 [ %4, %3 ], [ %8, %18 ]
  store i32 %29, ptr @u, align 4, !tbaa !5
  store i32 %28, ptr @v, align 4, !tbaa !5
  br label %30

30:                                               ; preds = %27, %16
  ret void
}

Note that - store to u, v both got sinked out of loop.

store i32 %29, ptr @u, align 4, !tbaa !5
store i32 %28, ptr @v, align 4, !tbaa !5

[gsocshubham]

What do you think about passing thread model information from clang to LICM?

a. I had to change lot many files just to pass a single bool variable - which seems not feasible.
b. I could not think of any other approach apart from above. Let me know if someone has a better approach.
c. Is there no way to know thread model from the optimizations? Is it just present in the clang frontend? Are there any other phases which uses thread model info?

[efriedma]

The clang changes are sort of right, in the sense that it's getting value of the right flag to the right place, but it's not how we pass around that sort of information.

Usually, we do one of two things:

• Treat it as a property of the target, and add a method to TargetTransformInfo to retrieve it from the target.
• Encode the information directly in the IR, as a function attribute or something like that.

llvm/lib/Transforms/Scalar/LICM.cpp

113

Since this is specifically for LICM, maybe call it licm-force-thread-model-single

[gsocshubham]

Change thread model single licm flag name to licm-force-thread-model-single from thread-model-single.

[gsocshubham]

In D130466#3719718, @efriedma wrote:

The clang changes are sort of right, in the sense that it's getting value of the right flag to the right place, but it's not how we pass around that sort of information.

Usually, we do one of two things:

• Treat it as a property of the target, and add a method to TargetTransformInfo to retrieve it from the target.

@efriedma - ThreadModel is available in TargetOptions, how can i make it visible in TargetTransformInfo?

1. I do not see any usage of ThreadModel in CodeGen/Transforms/Target. I see it in only in the front end.
2. The only way I can think of is to pass information from clang to CodeGen and then store it in TargetTransformInfo and then use it in LICM. Can you point me to an example which is already present which does it? It would be helpful.

Clang (exist here) -> CodeGen (how to store here) -> Transform(want to use here)

In above patch, I passed ThreadModel from Clang to Transform but passing from Clang to CodeGen seems correct. Can you point me to such example?

• Encode the information directly in the IR, as a function attribute or something like that.

The second approach does not seem feasible in this case as the information might be lost till the time it reaches LICM. I will go with (1).

[efriedma]

The ThreadModel is passed from clang->LLVM; see llvm/include/llvm/Target/TargetOptions.h

Most interesting parts of TargetTransformInfo are implemented in llvm/include/llvm/CodeGen/BasicTTIImpl.h . In there, you should be able to go from TargetLowering->TargetMachine->TargetOptions, or something like that.

[gsocshubham]

In D130466#3726690, @efriedma wrote:

The ThreadModel is passed from clang->LLVM; see llvm/include/llvm/Target/TargetOptions.h

Most interesting parts of TargetTransformInfo are implemented in llvm/include/llvm/CodeGen/BasicTTIImpl.h . In there, you should be able to go from TargetLowering->TargetMachine->TargetOptions, or something like that.

Makes sense.

One can get TargetOptions using - TargetLowering->getTargetMachine()->DefaultOptions->ThreadModel where DefaultOptions is TargetOptions only if TargetLowering is available in LICM.

1. Getting TargetLowering or TargetMachine in LICM does not seem pretty straight forward/directly available in LICM which implies there seems no way to know Thread Model in LICM.

-> In LICM, we have TargetTransformInfo and TargetLibraryInfo but again it does not fetch TargetLowering/TargetOptions in any way.

2. The current implementation seems complete as per https://github.com/llvm/llvm-project/issues/50537 in which there is option -licm-force-thread-model-single if the target supports thread model single.

3. We pass thread model from clang to licm which enables this transformation when thread model is single.

[gsocshubham]

@efriedma - WDYT?

If we can get TargetLowering/TargetMachine in LICM then we do not need to pass thread model from clang to LICM. But I do not see any optimization making use of TargetLowering/TargetMachine as it is unavailable. Do you have any suggestions on it?

[efriedma]

TargetTransformInfo can access TargetLowering. Set getTLI() in BasicTTIImpl.h.

[gsocshubham]

Fix review comments -

1. Rename LICM flag to -licm-force-thread-model-single

2. Use thread model info from TargetOptions instead of passing from clang to llvm

[gsocshubham]

In D130466#3736041, @efriedma wrote:

TargetTransformInfo can access TargetLowering. Set getTLI() in BasicTTIImpl.h.

Understood. I have updated it.

I have fixed all the suggestions. WDYT? @eli.friedman

[gsocshubham]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

112 ↗

(On Diff #454415)

What should be the return value here? Should it be ThreadModel::INVALID or should I keep it same?

Should I add a new value to existing enum like below?

namespace ThreadModel {
  enum Model {
    INVALID // Thread model not known?
    POSIX,  // POSIX Threads
    Single  // Single Threaded Environment
  };
}

Above enum is defined in llvm/Target/TargetOptions.h

[gsocshubham]

Use Options instead of DefaultOptions while fetching thread model.

[gsocshubham]

Any review comments - @momchil.velikov @eli.friedman

[efriedma]

I think that instead of "ThreadModel::Model getThreadModel()" as the TTI API, we should just make the API something like "bool isSingleThreaded()". Which is basically, can any other thread run at the "same" time. I don't really want to include TargetOptions.h everywhere, and it makes the reason we're exposing it on TargetTransformInfo a bit more clear.

I don't think you ever addressed my comment about constants. The case where that would come up as a practical issue is if you have an argument marked "deferenceable"; we know it's legal to load from an arbitrary dereferenceable pointer, but it's not legal to store to one. We can only store to locations we know are modifiable (allocas, non-constant global variables, etc.)

[gsocshubham]

1. Change ThreadModel::Model getThreadModel() to bool isSingleThreaded()

2. Remove inclusion of TargetOptions at various places.

3. Prohibit this transformation if store points to constant memory using bool PointToConstantMemory.

[gsocshubham]

In D130466#3752338, @efriedma wrote:

I think that instead of "ThreadModel::Model getThreadModel()" as the TTI API, we should just make the API something like "bool isSingleThreaded()". Which is basically, can any other thread run at the "same" time. I don't really want to include TargetOptions.h everywhere, and it makes the reason we're exposing it on TargetTransformInfo a bit more clear.

Understood. Updated as above.
Thanks!

I don't think you ever addressed my comment about constants. The case where that would come up as a practical issue is if you have an argument marked "deferenceable"; we know it's legal to load from an arbitrary dereferenceable pointer, but it's not legal to store to one. We can only store to locations we know are modifiable (allocas, non-constant global variables, etc.)

I have added a check to avoid this transformation if store points to constant memory. Let me know WDYT on it. Have I addressed all your comments now? @eli.friedman

[efriedma]

Prohibit this transformation if store points to constant memory using bool PointToConstantMemory.

You can't use pointsToConstantMemory to prove the property you need. The problem is that it doesn't do what you want if it can't prove anything. You need a function that says the memory isn't writable unless it can prove the memory is writable (maybe call it something like "pointsToWritableMemory").

Getting the proof requirements wrong is a common trap for newcomers to writing compiler optimizations; please watch out for it in the future.

[nikic]

In D130466#3761744, @efriedma wrote:

Prohibit this transformation if store points to constant memory using bool PointToConstantMemory.

You can't use pointsToConstantMemory to prove the property you need. The problem is that it doesn't do what you want if it can't prove anything. You need a function that says the memory isn't writable unless it can prove the memory is writable (maybe call it something like "pointsToWritableMemory").

Getting the proof requirements wrong is a common trap for newcomers to writing compiler optimizations; please watch out for it in the future.

In practice, would that be alloca and non-constant globals, or can we handle any other cases as well? I don't think doing this for noalias calls would be legal, because the noalias semantics don't say anything about the memory being writable, right?

llvm/test/Transforms/LICM/promote-sink-store.ll

1 ↗

(On Diff #456922)

Please run the tests through -instnamer so the instructions have names. Also, it should be able to significantly reduce this test, it currently contains code not relevant to the transform.

You'll also want to add a negative test for the constant memory case.

[nikic]

In D130466#3763325, @nikic wrote:

In practice, would that be alloca and non-constant globals, or can we handle any other cases as well? I don't think doing this for noalias calls would be legal, because the noalias semantics don't say anything about the memory being writable, right?

Hm ... we already assume that this is fine for noalias calls (in the non-capturing case), so I guess that's a pre-existing issue that is orthogonal to this patch. I believe the right treatment here would be to only omit the isNotCapturedBeforeOrInLoop() check in the single-thread case, but leave everything else alone.

[gsocshubham]

In D130466#3761744, @efriedma wrote:

Prohibit this transformation if store points to constant memory using bool PointToConstantMemory.

You can't use pointsToConstantMemory to prove the property you need. The problem is that it doesn't do what you want if it can't prove anything. You need a function that says the memory isn't writable unless it can prove the memory is writable (maybe call it something like "pointsToWritableMemory").

Understood. Should I add isNotCapturedBeforeOrInLoop() as an extra check as mentioned by @nikic ?

Getting the proof requirements wrong is a common trap for newcomers to writing compiler optimizations; please watch out for it in the future.

Noted. Thanks!

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store.ll

1 ↗

(On Diff #456922)

Sure. I will update it in the next push once we finalize the check on whether to use isNotCapturedBeforeOrInLoop() or should we write a custom function pointsToWritableMemory() to check alloca and non-constant globals?

[efriedma]

In D130466#3766569, @gsocshubham wrote:

In D130466#3761744, @efriedma wrote:

Prohibit this transformation if store points to constant memory using bool PointToConstantMemory.

You can't use pointsToConstantMemory to prove the property you need. The problem is that it doesn't do what you want if it can't prove anything. You need a function that says the memory isn't writable unless it can prove the memory is writable (maybe call it something like "pointsToWritableMemory").

Understood. Should I add isNotCapturedBeforeOrInLoop() as an extra check as mentioned by @nikic ?

First off, please rebase your patch on main; @nikic made changes in rG315aef66.

Anyway, with that patch, the relevant bit of code currently looks like this:

Value *Object = getUnderlyingObject(SomePtr);
SafeToInsertStore =
    (isNoAliasCall(Object) || isa<AllocaInst>(Object) ||
     (isa<Argument>(Object) && cast<Argument>(Object)->hasByValAttr())) &&
    isNotCapturedBeforeOrInLoop(Object, CurLoop, DT);

There are basically two checks here: one, that the location is readable and writable (it's a malloc/alloca/byval argument/etc,), and two, that the location isn't accessed by some other thread (isNotCapturedBeforeOrInLoop).

If you know there aren't any other threads, you can just skip the isNotCapturedBeforeOrInLoop() check, and you're basically done.

On top of that, you probably also want to expand the list of locations that are known to be readable and writable to include global variables. (The current code doesn't check for them because the isNotCapturedBeforeOrInLoop() check can't succeed for global variables.)

[nikic]

I pushed another change that should make this code clearer: https://github.com/llvm/llvm-project/commit/388b684354cc71bd4043ddccbcfd91fb338d8b1e In single-thread mode, the isThreadLocalObject() check can be skipped. isWritableObject() can be extended to handle constant globals.

[gsocshubham]

Address review comments.

Run -instnamer on lit tests.

TODO - Add a negative test for the constant memory case.

I am thinking on what changes needs to be done on below testcase to become it as negative test -

int u, v;

void f(int a[restrict], int b[restrict], int n) {

for (int i = 0; i < n; ++i) {
    if (a[i]) {
        ++u;
        break;
    }
    ++u;
    if (b[i])
        ++v;
}

}

[gsocshubham]

I had rebased with master while pushing changes. But while pushing, some other patch got merged which causes conflict.

Let me rebase it again and push it again.

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store.ll

1 ↗

(On Diff #456922)

@nikic - Can you please point me to a testcase for constant memory case?

[gsocshubham]

Add global variable check for sinking store.

[gsocshubham]

In D130466#3776571, @gsocshubham wrote:

Add global variable check for sinking store.

@eli.friedman @nikic - Can you please give review on my latest changes?

[gsocshubham]

Update SafeToInsertStore check.

[gsocshubham]

Fix build bot failure caused by change in clang-format version.

Combine thread model single check with global variable check.

[gsocshubham]

@eli.friedman and @nikic - Any thoughts on above changes?

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2111

The check for GlobalVariable should go inside isWritableObject() and needs to check !isConstant().

[xbolva00]

llvm/lib/Transforms/Scalar/LICM.cpp

114

You should rename this variable.

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

114

Do you have any suggestion? Probably, ForceThreadModelSingle?

[gsocshubham]

Fix all review comments -

1. Move global variable constant check inside IsWritableObject()

2. Rename flag ThreadModelSingle to SingleThread

llvm/lib/Transforms/Scalar/LICM.cpp

114

I have renamed flag to SingleThread.

@xbolva00 - Let me know WDYT

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2110–2111

These checks should be in isThreadLocalObject(). If there is only a single thread, then the object is always thread-local. Your current code incorrectly skips the writability check.

[gsocshubham]

Move checks (TTI->isSingleThreaded() || SingleThread) inside bool isThreadLocalObject()

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

2110–2111

Done. Thanks!

Please check it.

[gsocshubham]

Is this patch ready to be merged?

@nikic @dmgreen @eli.friedman

[nikic]

I believe the logic is now correct, but testing could be improved. Some suggestions:

• Use a single file with two RUN lines, only one of which has -licm-force-thread-model-single. Combined with --check-prefixes, this will make it clear in which cases behavior differs based on the flag and in which cases it is the same.
• The current test cases look too complicated. For globals, I believe a very simple loop that just loads / stores the global inside the loop should be enough. Without the flag this will lead to only load promotion, and with it to store promotion.
• We should have a variant of that test with a constant global (should have no store promotion, independent of the flag).
• We should have a variant of the test with a function argument (unknown if writable, so should have no store promotion).
• We should have a variant of the test with an alloca that is captured (store promotion legal with the flag, because capture does not impact thread safety).

llvm/lib/Transforms/Scalar/LICM.cpp

1908

Unused AAResults argument?

[gsocshubham]

Add unit tests.

TODO - Remove attributes from test cases.

[gsocshubham]

1. Remove attributes from LIT tests.

2. Run --instnamer on LIT tests.

3. Rename testcases as below -

promote-sink-store-arg.ll
-> No store promotion

promote-sink-store-capture.ll
-> Store promotion

promote-sink-store-constant-global.ll
-> No store promotion

promote-sink-store-global.ll
-> Store promotion

[gsocshubham]

@nikic @efriedma - Can you please give review on latest LIT tests? Is there any other way to remove alloca apart from mem2reg? Using mem2reg changes state of the program where I want to show current optimization.

I will rebase patch and update it since failure is due to ongoing patches in master.

[gsocshubham]

PING - @nikic @eli.friedman

[gsocshubham]

Rebase with master branch.

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

1908

Removed.

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store.ll

3 ↗

(On Diff #462391)

FTMS stands for Force Thread Model Single
NFTMS stands for No Force Thread Model Single

[gsocshubham]

Address all the review comments.

1. Add 2 RUN lines in LIT tests with prefixes - LICM-TMS and LICM-NO-TMS where TMS stands for Thread Model Single

2. Add a minimal test for globals where store promotion will happen only if flag is set and load promotion happens irrespective of the flag.

-> promote-sink-store-global.ll

3. Add a minimal test for constant globals where store promotion will not happen irrespective of the flag.

-> promote-sink-store-constant-global.ll

4. Add a minimal test for function argument where store promotion will not happen.

-> promote-sink-store-arg.ll

5. Add a minimal test for alloca that is captured where store promotion will happen.

-> promote-sink-store-capture.ll

6. At last there is a testcase named - "promote-sink-store.ll" which is the testcase attached in original bug description from github - https://github.com/llvm/llvm-project/issues/50537

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store-arg.ll

73 ↗

(On Diff #463654)

This IR is obtained from below C code -

void f(int n, int u) {
    for (int i = 0; i < n; ++i) {
            u = i;
    }
}

llvm/test/Transforms/LICM/promote-sink-store-constant-global.ll

77 ↗

(On Diff #463654)

This IR is obtained from C testcase -

const int u = 7;

void f(int n) {
     int x;
    for (int i = 0; i < n; ++i) {
        x = u;
    }
}

llvm/test/Transforms/LICM/promote-sink-store-global.ll

85 ↗

(On Diff #463654)

This IR is obtained from C code -

int u, v;

void f(int n) {
    int a;
    for (int i = 0; i < n; ++i) {
            u = i;
            a = v;
    }
}

llvm/test/Transforms/LICM/promote-sink-store.ll

91 ↗

(On Diff #463654)

This IR is obtained from below testcase attached from bug description -

int u, v;

void f(int a[restrict], int b[restrict], int n) {
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            ++u;
            break;
        }
        ++u;
        if (b[i])
            ++v;
    }
}

[gsocshubham]

In D130466#3783514, @nikic wrote:

I believe the logic is now correct, but testing could be improved. Some suggestions:

• Use a single file with two RUN lines, only one of which has -licm-force-thread-model-single. Combined with --check-prefixes, this will make it clear in which cases behavior differs based on the flag and in which cases it is the same.

Added 2 RUN lines in all the LIT tests.

• The current test cases look too complicated. For globals, I believe a very simple loop that just loads / stores the global inside the loop should be enough. Without the flag this will lead to only load promotion, and with it to store promotion.

I have used a simple loop to achieve above.

• We should have a variant of that test with a constant global (should have no store promotion, independent of the flag).

Done.

• We should have a variant of the test with a function argument (unknown if writable, so should have no store promotion).

Done.

• We should have a variant of the test with an alloca that is captured (store promotion legal with the flag, because capture does not impact thread safety).

Done.

[gsocshubham]

Review request - @momchil.velikov @dmgreen @eli.friedman @nikic @fhahn

Can someone give final review? If this patch is fine, is it ready to merge?

All review comments have been addressed with no regression.

[gsocshubham]

Use below testcase for capture case - test/Transforms/LICM/promote-sink-store-capture.ll

void f(int n, int u) {
    for (int i = 0, x = u; i < n; ++i) {
    x = i;
    }
}

instead of -

void f(int a[restrict], int n, int u) {
    for (int i = 0; i < n; ++i) {
    int x = u;
        if (a[i]) {
            ++x;
            break;
        }
        ++x;
    }
}

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store-capture.ll

83 ↗

(On Diff #463767)

C testcase which is used to generate below IR -

void f(int n, int u) {
    for (int i = 0, x = u; i < n; ++i) {
    x = i;
    }
}

Note - For capture case, store promotion happens irrespective of flag -licm-force-thread-model-single i.e. with just -licm with current state of LICM.

In my last to last revision, without that flag captured store promotion was not happening, maybe some other patches in between have caused it.

[nikic]

Can you please run the test cases through -sroa (as in, commit the test case with SROA applied, not add it to the RUN line)? The current tests contain unnecessary alloca+load/store+lifetime.start/end.

llvm/lib/Transforms/Scalar/LICM.cpp

115

Update description to match new option name?

[arsenm]

llvm/test/Transforms/LICM/promote-sink-store-arg.ll

98 ↗

(On Diff #463767)

How is the threadedness relevant in a case that doesn't use atomic loads and stores?

[gsocshubham]

Address review comments -

1. Run -sroa on lit tests where-ever applicable.

2. Update LICM flag description.

3. Add a new LIT test "promote-sink-atomic-store-arg.ll" to show atomic store behaviour.

I am able to run -sroa successfully on promote-sink-store-global.ll

I could not run sroa on below LIT tests as everything is getting optimized and there will be no load/store left to showcase this optmization effect - (Please check below godbolt links)

a. promote-sink-store-constant-global.ll - Constant global case - https://clang.godbolt.org/z/n5E69ebbz

IR obtained from -

const int u = 7;

int f(int n) {
     int x, i;
    for (i = 0; i < n; ++i) {
        x = u;
    }
  return x + u;
}

b. promote-sink-store-capture.ll - Capture case - https://clang.godbolt.org/z/fjxn7xc46

IR obtained from -

void f(int n, int u) {
    for (int i = 0, x = u; i < n; ++i) {
    x = u;
    }
}

c. promote-sink-store-arg.ll - Function argument case - https://clang.godbolt.org/z/d85qhxbsr

IR obtained from -

void f(int n, int u) {
    for (int i = 0; i < n; ++i) {
            u = i;
    }
}

[gsocshubham]

llvm/lib/Transforms/Scalar/LICM.cpp

115

Done.

llvm/test/Transforms/LICM/promote-sink-atomic-store-arg.ll

73 ↗

(On Diff #464209)

This IR is obtained from below C testcase -

void f(int n, int u) {
    for (int i = 0; i < n; ++i) {
    __atomic_store_n( &u, i, __ATOMIC_SEQ_CST );
    }
}

llvm/test/Transforms/LICM/promote-sink-store-arg.ll

98 ↗

(On Diff #463767)

I have added a new test named - promote-sink-atomic-store-arg.ll below which contains atomic store.

Let me know WDYT of the new test.

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store-global.ll

85 ↗

(On Diff #463654)

Now the latest IR is being generated using below C code followed by -sroa

int u, v;

int f(int n) {
    int a;
    for (int i = 0; i < n; ++i) {
            u = i;
            a = v;
    }
  return u + a;
}

[gsocshubham]

@nikic - Does the patch look fine now? Is it ready to merge?

Let me know suggestions if any. Thanks for your earlier -sroa comment.

[gsocshubham]

In D130466#3827345, @gsocshubham wrote:

@nikic - Does the patch look fine now? Is it ready to merge?

Let me know suggestions if any. Thanks for your earlier -sroa comment.

PING.

[gsocshubham]

In D130466#3824014, @nikic wrote:

Can you please run the test cases through -sroa (as in, commit the test case with SROA applied, not add it to the RUN line)? The current tests contain unnecessary alloca+load/store+lifetime.start/end.

I have run -sroa and shared respective dumps.

Please let me know if you need any other changes in this current patch.

llvm/lib/Transforms/Scalar/LICM.cpp

115

@nikic - Updated the description.

llvm/test/Transforms/LICM/promote-sink-store-arg.ll

98 ↗

(On Diff #463767)

@arsenm - Any thoughts on above?

[gsocshubham]

In D130466#3783514, @nikic wrote:

I believe the logic is now correct, but testing could be improved. Some suggestions:

• Use a single file with two RUN lines, only one of which has -licm-force-thread-model-single. Combined with --check-prefixes, this will make it clear in which cases behavior differs based on the flag and in which cases it is the same.
• The current test cases look too complicated. For globals, I believe a very simple loop that just loads / stores the global inside the loop should be enough. Without the flag this will lead to only load promotion, and with it to store promotion.
• We should have a variant of that test with a constant global (should have no store promotion, independent of the flag).
• We should have a variant of the test with a function argument (unknown if writable, so should have no store promotion).
• We should have a variant of the test with an alloca that is captured (store promotion legal with the flag, because capture does not impact thread safety).

Should I keep both prefix checks with and without flag? That is increasing number of lines of code in the testcase.

After reducing the testcase with bare minumum load/store licm opt - Below are number of lines

promote-sink-atomic-store-arg.ll - 30 lines
promote-sink-store-arg.ll - 30 lines
promote-sink-store-capture.ll - 40 lines
promote-sink-store-constant-global.ll - 20 lines
promote-sink-store-global.ll - 20 lines
promote-sink-store.ll - 35 lines

+ checks generated by llvm/utils
+ these includes spaces in between

[gsocshubham]

Add simple LIT tests -

1. Remove complex testcases and add simple ones without allocas as requested by @nikic
2. Run -instnamer and -sroa.
3. Two checks with and without flag -licm-force-thread-model-single is shown only when behaviour differs when flag is set. (For reduced line in LIT tests). TMS stands for Thread Model Single

Note - There is alloca present in capture case as requested from above comment by @nikic We should have a variant of the test with an alloca that is captured (store promotion legal with the flag, because capture does not impact thread safety).

Behaviour of test cases -

constant-global-sroa-instnamer.ll
-> We can not store to a constant global and hence same behaviour irrespective of flag

capture-instnamer.ll
-> Store promotion happens.

arg-sroa-instnamer.ll
-> No store promotion irrespective of flag.

promote-sink-store-global.ll
-> Store promotion happens if flag is set.

[gsocshubham]

llvm/test/Transforms/LICM/promote-sink-store-arg.ll

73 ↗

(On Diff #463654)

Updated test IR is obtained after running -sroad and -instnamer on -

int i, n;

void f(int u[n]) {
    for (i = 0; i < n; ++i) {
          if(u[i])
            u[i] = i;
    }
}

Here store to u will be not promoted.

llvm/test/Transforms/LICM/promote-sink-store-capture.ll

83 ↗

(On Diff #463767)

Updated test IR is obtained after running -sroad and -instnamer on -

int i;

void f(int u) {
    i = 0;
    for (int x = u; i < 20; ++i) {
    x = i;
    }
}

Here store to x will be promoted.

llvm/test/Transforms/LICM/promote-sink-store-constant-global.ll

77 ↗

(On Diff #463654)

Updated test IR is obtained after running -sroad and -instnamer on -

const int u;

int f(int n) {
     int x, i;
    for (i = 0; i < n; ++i) {
        x = u;
    }
  return x + u;
}

[nikic]

I'm still not really happy with the minimality of these tests. They still contain many unnecessary parts. Generally, unless you are writing debuginfo tests, it is better to write test IR by hand instead of trying to generate it using clang.

I've pushed a set of minimal tests at https://github.com/llvm/llvm-project/commit/b6676f3c12588cd1333de9bb3cee3a53bc71771e. Can you please rebase over those tests, and then rerun update_test_checks.py with these adjusted RUN lines?

; RUN: opt -S -licm < %s | FileCheck %s --check-prefixes=CHECK,MT
; RUN: opt -S -licm -licm-force-thread-model-single < %s | FileCheck %s --check-prefixes=CHECK,ST

[gsocshubham]

Update RUN lines with flag -licm-force-thread-model-single and rerun update_test_checks.py on promote-single-thread.ll

Remove previously submitted LIT tests.

[gsocshubham]

In D130466#3842927, @nikic wrote:

I'm still not really happy with the minimality of these tests. They still contain many unnecessary parts. Generally, unless you are writing debuginfo tests, it is better to write test IR by hand instead of trying to generate it using clang.

Understood!

I've pushed a set of minimal tests at https://github.com/llvm/llvm-project/commit/b6676f3c12588cd1333de9bb3cee3a53bc71771e. Can you please rebase over those tests, and then rerun update_test_checks.py with these adjusted RUN lines?

; RUN: opt -S -licm < %s | FileCheck %s --check-prefixes=CHECK,MT
; RUN: opt -S -licm -licm-force-thread-model-single < %s | FileCheck %s --check-prefixes=CHECK,ST

@nikic - Thanks a lot for above tests. I have rebased and updated it accordingly.

Now, store in promote_global() and promote_captured_alloca() gets promoted as per your comments in the testcase. Is this patch good to merge now?

[nikic]

LGTM

[gsocshubham]

In D130466#3843156, @nikic wrote:

LGTM

Thanks. Can you please commit it for me with below details? I do not have commit access.

Name - Shubham Narlawar
Email - [e-mail]

"Shubham Narlawar <[e-mail]>"

[nikic]

Sure, I'll land this on Monday if nobody beats me to it.

[arsenm]

How is this different from using syncscope("singlethread")?

[nikic]

In D130466#3844483, @arsenm wrote:

How is this different from using syncscope("singlethread")?

They don't have any relation, syncscope is a property of atomic operations.

To remove all the LICM-specific aspects, the question here is basically whether it is safe to introduce a spurious (non-atomic) store of the form store (load p), p without introducing a data race.

[gsocshubham]

In D130466#3843921, @nikic wrote:

Sure, I'll land this on Monday if nobody beats me to it.

Sounds good.

It seems like everyone is fine with it!

[gsocshubham]

@nikic - Thanks for comitting it.

Thanks for your help!

[Bhramar.vatsa]

We see that for a single-threaded system or with option '-mllvm -licm-force-thread-model-single', the generated code quality worsens for a very simple example: https://godbolt.org/z/5xhY1EcGb.

Would it be possible to fix this?

[nikic]

In D130466#4174726, @Bhramar.vatsa wrote:

We see that for a single-threaded system or with option '-mllvm -licm-force-thread-model-single', the generated code quality worsens for a very simple example: https://godbolt.org/z/5xhY1EcGb.

Would it be possible to fix this?

This is not really a regression at the IR level. Ideally the loop would be removed entirely after indvars loop exit replacement, but it currently doesn't support this pattern where the value from the next-to-last iteration is taken. There's a couple open issues for that, but somehow I can't find a single one of them...

[nikic]

Ah, I found one of the issues I remembered: https://github.com/llvm/llvm-project/issues/51396

[Bhramar.vatsa]

Yes, it looks like the similar conditions are triggered by the code shown in that issue, but perhaps the reason isn't that indvars simplification pass couldn't really deduce the the value from last but one iteration (as seen in the example I shared: https://godbolt.org/z/5xhY1EcGb), but maybe the code structure introduced by this change?

The indvarsimplify did work fine in the absence of the option '-licm-force-thread-model-single'. With this option, the store is sunk into exit block in the first pass of LICM itself (just before loop-rotation). This then presents a different loop body to loop-rotation, which doesn't result in a guard condition. In the end, indvarsimplification see the exit block depending upon not just the induction variable value, but also on the original value of 'theGlobalVar', which perhaps make it difficult to reduce this to just an exit val computation.

As opposed to this, the case where it works (without the LICM option), the indvar simplification sees the loop as invariant i.e. the exit values just depends upon only the values from within loop, which then perhaps helps in reducing the loop to just an exit value computation.

In other words, with this LICM change, the store, which otherwise was getting skipped is now always done, making the code in the exit block to choose between the two values to store, the original value of global or the one less than exit value from the loop. The original value of the global location is propagated through loop making it more complicated than required? So, perhaps this is not required, but instead the code can be transformed such that the choice of values can be directly done in the exit block (e.g. a select between original value or computed exit val based on loop condition, similar to loop-rotation's guard condition)? This will leave the loop only with induction variable computations and thus can still be just reduced to calculation of exit values.
However, I do understand that this might out of scope of this change as it didn't introduce the transformation, but just exploited it.

llvm/lib/Transforms/Scalar/LICM.cpp

 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetOptions.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <utility>

 static cl::opt<bool>
     DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
                      cl::desc("Disable memory promotion in LICM pass"));
 
 static cl::opt<bool> ControlFlowHoisting(
     "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
     cl::desc("Enable control flow (and PHI) hoisting in LICM"));
 
 static cl::opt<uint32_t> MaxNumUsesTraversed(
     "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 // Experimental option to allow imprecision in LICM in pathological cases, in
 // exchange for faster compile. This is to be removed if MemorySSA starts to
 // address the same issue. LICM calls MemorySSAWalker's
 // getClobberingMemoryAccess, up to the value of the Cap, getting perfect
 // accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
 // which may not be precise, since optimizeUses is capped. The result is
for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
         NewMemAcc = MSSAU.createMemoryAccessInBB(
             NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
       } else {
         NewMemAcc =
             MSSAU.createMemoryAccessAfter(NewSI, nullptr, MSSAInsertPoint);
       }
       MSSAInsertPts[i] = NewMemAcc;
       MSSAU.insertDef(cast<MemoryDef>(NewMemAcc), true);
       // FIXME: true for safety, false may still be correct.
     }
   }
 
   void doExtraRewritesBeforeFinalDeletion() override {
     if (CanInsertStoresInExitBlocks)
       insertStoresInLoopExitBlocks();
   }
 

 } // namespace
 
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(
     const SmallSetVector<Value *, 8> &PointerMustAliases,
     SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts,
     SmallVectorImpl<MemoryAccess *> &MSSAInsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
     Loop *CurLoop, MemorySSAUpdater &MSSAU, ICFLoopSafetyInfo *SafetyInfo,
     OptimizationRemarkEmitter *ORE, bool AllowSpeculation) {
   // Verify inputs.
   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
bool llvm::promoteLoopAccessesToScalars(
   // atomics.
   if (SawUnorderedAtomic && Alignment < MDL.getTypeStoreSize(AccessTy))
     return false;
 
   // If we couldn't prove we can hoist the load, bail.
   if (!DereferenceableInPH)
     return false;
 
   // We know we can hoist the load, but don't have a guaranteed store.
   // Check whether the location is thread-local. If it is, then we can insert
   // stores along paths which originally didn't have them without violating the
   // memory model.
   if (!SafeToInsertStore) {
-    if (IsKnownThreadLocalObject)
+    if (IsKnownThreadLocalObject || ThreadModel::Single)
       SafeToInsertStore = true;
     else {
       Value *Object = getUnderlyingObject(SomePtr);
       SafeToInsertStore =
           (isNoAliasCall(Object) || isa<AllocaInst>(Object)) &&
           isNotCapturedBeforeOrInLoop(Object, CurLoop, DT);
     }
   }

llvm/test/Transforms/LICM/hoist-load-without-store.ll

 ; CHECK-NEXT:    [[PTR_PROMOTED:%.*]] = load i32, i32* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[PTR_PROMOTED]], [[FOR_BODY_LR_PH]] ], [ 1, [[IF_END:%.*]] ]
 ; CHECK-NEXT:    [[I_08:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[IF_END]] ]
 ; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[TMP0]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END]], label [[FOR_BODY_CLEANUP1_CRIT_EDGE:%.*]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i32 1, i32* [[PTR]], align 4
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_08]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[N]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP1_CRIT_EDGE:%.*]]
 ; CHECK:       for.body.cleanup1_crit_edge:
+; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP0]], [[FOR_BODY]] ]
+; CHECK-NEXT:    store i32 [[DOTLCSSA]], i32* [[PTR]], align 4
 ; CHECK-NEXT:    br label [[CLEANUP1]]
 ; CHECK:       for.cond.cleanup1_crit_edge:
+; CHECK-NEXT:    store i32 1, i32* [[PTR]], align 4
 ; CHECK-NEXT:    br label [[CLEANUP1]]
 ; CHECK:       cleanup1:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp7 = icmp slt i32 0, %n
   br i1 %cmp7, label %for.body.lr.ph, label %cleanup1
 

llvm/test/Transforms/LICM/promote-capture.ll

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[C_INC2:%.*]] = phi i32 [ [[COUNT_PROMOTED]], [[ENTRY:%.*]] ], [ [[C_INC1:%.*]], [[LATCH:%.*]] ]
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[I_NEXT:%.*]], [[LATCH]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond(i32 [[I]])
 ; CHECK-NEXT:    br i1 [[COND]], label [[IF:%.*]], label [[LATCH]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[C_INC:%.*]] = add i32 [[C_INC2]], 1
-; CHECK-NEXT:    store i32 [[C_INC]], i32* [[COUNT]], align 4
 ; CHECK-NEXT:    br label [[LATCH]]
 ; CHECK:       latch:
 ; CHECK-NEXT:    [[C_INC1]] = phi i32 [ [[C_INC]], [[IF]] ], [ [[C_INC2]], [[LOOP]] ]
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I_NEXT]], [[LEN:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
+; CHECK-NEXT:    [[C_INC1_LCSSA:%.*]] = phi i32 [ [[C_INC1]], [[LATCH]] ]
+; CHECK-NEXT:    store i32 [[C_INC1_LCSSA]], i32* [[COUNT]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %count = alloca i32
   store i32 0, i32* %count
   call void @capture(i32* %count)
   br label %loop
 

llvm/test/Transforms/LICM/reg-promote.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -licm -S %s | FileCheck %s
+
+target triple = "aarch64-unknown-linux"
+
+@u = dso_local global i32 0, align 4
+@v = dso_local global i32 0, align 4
+@restrict = dso_local global i32 0, align 4
+@i = dso_local global i32 0, align 4
+
+; Function Attrs: mustprogress nounwind uwtable
+define dso_local void @_Z1fPiS_i(ptr noundef %0, ptr noundef %1, i32 noundef %2) #0 {
+; CHECK-LABEL: @_Z1fPiS_i(
+; CHECK-NEXT:    [[TMP4:%.*]] = alloca ptr, align 8
+; CHECK-NEXT:    [[TMP5:%.*]] = alloca ptr, align 8
+; CHECK-NEXT:    [[TMP6:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store ptr [[TMP0:%.*]], ptr [[TMP4]], align 8
+; CHECK-NEXT:    store ptr [[TMP1:%.*]], ptr [[TMP5]], align 8
+; CHECK-NEXT:    store i32 [[TMP2:%.*]], ptr [[TMP6]], align 4
+; CHECK-NEXT:    [[TMP7:%.*]] = load i32, ptr @restrict, align 4
+; CHECK-NEXT:    [[TMP8:%.*]] = zext i32 [[TMP7]] to i64
+; CHECK-NEXT:    [[TMP9:%.*]] = load i32, ptr @restrict, align 4
+; CHECK-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
+; CHECK-NEXT:    store i32 0, ptr @i, align 4
+; CHECK-NEXT:    [[TMP11:%.*]] = load i32, ptr [[TMP6]], align 4
+; CHECK-NEXT:    [[TMP12:%.*]] = load ptr, ptr [[TMP4]], align 8
+; CHECK-NEXT:    [[TMP13:%.*]] = load ptr, ptr [[TMP5]], align 8
+; CHECK-NEXT:    br label [[TMP14:%.*]]
+; CHECK:       14:
+; CHECK-NEXT:    [[TMP15:%.*]] = load i32, ptr @i, align 4
+; CHECK-NEXT:    [[TMP16:%.*]] = icmp slt i32 [[TMP15]], [[TMP11]]
+; CHECK-NEXT:    br i1 [[TMP16]], label [[TMP17:%.*]], label [[DOTLOOPEXIT:%.*]]
+; CHECK:       17:
+; CHECK-NEXT:    [[TMP18:%.*]] = load i32, ptr @i, align 4
+; CHECK-NEXT:    [[TMP19:%.*]] = sext i32 [[TMP18]] to i64
+; CHECK-NEXT:    [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[TMP12]], i64 [[TMP19]]
+; CHECK-NEXT:    [[TMP21:%.*]] = load i32, ptr [[TMP20]], align 4
+; CHECK-NEXT:    [[TMP22:%.*]] = icmp ne i32 [[TMP21]], 0
+; CHECK-NEXT:    br i1 [[TMP22]], label [[TMP23:%.*]], label [[TMP26:%.*]]
+; CHECK:       23:
+; CHECK-NEXT:    [[TMP24:%.*]] = load i32, ptr @u, align 4
+; CHECK-NEXT:    [[TMP25:%.*]] = add nsw i32 [[TMP24]], 1
+; CHECK-NEXT:    store i32 [[TMP25]], ptr @u, align 4
+; CHECK-NEXT:    br label [[TMP41:%.*]]
+; CHECK:       26:
+; CHECK-NEXT:    [[TMP27:%.*]] = load i32, ptr @u, align 4
+; CHECK-NEXT:    [[TMP28:%.*]] = add nsw i32 [[TMP27]], 1
+; CHECK-NEXT:    store i32 [[TMP28]], ptr @u, align 4
+; CHECK-NEXT:    [[TMP29:%.*]] = load i32, ptr @i, align 4
+; CHECK-NEXT:    [[TMP30:%.*]] = sext i32 [[TMP29]] to i64
+; CHECK-NEXT:    [[TMP31:%.*]] = getelementptr inbounds i32, ptr [[TMP13]], i64 [[TMP30]]
+; CHECK-NEXT:    [[TMP32:%.*]] = load i32, ptr [[TMP31]], align 4
+; CHECK-NEXT:    [[TMP33:%.*]] = icmp ne i32 [[TMP32]], 0
+; CHECK-NEXT:    br i1 [[TMP33]], label [[TMP34:%.*]], label [[TMP37:%.*]]
+; CHECK:       34:
+; CHECK-NEXT:    [[TMP35:%.*]] = load i32, ptr @v, align 4
+; CHECK-NEXT:    [[TMP36:%.*]] = add nsw i32 [[TMP35]], 1
+; CHECK-NEXT:    store i32 [[TMP36]], ptr @v, align 4
+; CHECK-NEXT:    br label [[TMP37]]
+; CHECK:       37:
+; CHECK-NEXT:    br label [[TMP38:%.*]]
+; CHECK:       38:
+; CHECK-NEXT:    [[TMP39:%.*]] = load i32, ptr @i, align 4
+; CHECK-NEXT:    [[TMP40:%.*]] = add nsw i32 [[TMP39]], 1
+; CHECK-NEXT:    store i32 [[TMP40]], ptr @i, align 4
+; CHECK-NEXT:    br label [[TMP14]]
+; CHECK:       .loopexit:
+; CHECK-NEXT:    br label [[TMP41]]
+; CHECK:       41:
+; CHECK-NEXT:    ret void
+;
+  %4 = alloca ptr, align 8
+  %5 = alloca ptr, align 8
+  %6 = alloca i32, align 4
+  store ptr %0, ptr %4, align 8
+  store ptr %1, ptr %5, align 8
+  store i32 %2, ptr %6, align 4
+  %7 = load i32, ptr @restrict, align 4
+  %8 = zext i32 %7 to i64
+  %9 = load i32, ptr @restrict, align 4
+  %10 = zext i32 %9 to i64
+  store i32 0, ptr @i, align 4
+  br label %11
+
+11:                                               ; preds = %38, %3
+  %12 = load i32, ptr @i, align 4
+  %13 = load i32, ptr %6, align 4
+  %14 = icmp slt i32 %12, %13
+  br i1 %14, label %15, label %41
+
+15:                                               ; preds = %11
+  %16 = load ptr, ptr %4, align 8
+  %17 = load i32, ptr @i, align 4
+  %18 = sext i32 %17 to i64
+  %19 = getelementptr inbounds i32, ptr %16, i64 %18
+  %20 = load i32, ptr %19, align 4
+  %21 = icmp ne i32 %20, 0
+  br i1 %21, label %22, label %25
+
+22:                                               ; preds = %15
+  %23 = load i32, ptr @u, align 4
+  %24 = add nsw i32 %23, 1
+  store i32 %24, ptr @u, align 4
+  br label %41
+
+25:                                               ; preds = %15
+  %26 = load i32, ptr @u, align 4
+  %27 = add nsw i32 %26, 1
+  store i32 %27, ptr @u, align 4
+  %28 = load ptr, ptr %5, align 8
+  %29 = load i32, ptr @i, align 4
+  %30 = sext i32 %29 to i64
+  %31 = getelementptr inbounds i32, ptr %28, i64 %30
+  %32 = load i32, ptr %31, align 4
+  %33 = icmp ne i32 %32, 0
+  br i1 %33, label %34, label %37
+
+34:                                               ; preds = %25
+  %35 = load i32, ptr @v, align 4
+  %36 = add nsw i32 %35, 1
+  store i32 %36, ptr @v, align 4
+  br label %37
+
+37:                                               ; preds = %34, %25
+  br label %38
+
+38:                                               ; preds = %37
+  %39 = load i32, ptr @i, align 4
+  %40 = add nsw i32 %39, 1
+  store i32 %40, ptr @i, align 4
+  br label %11
+
+41:                                               ; preds = %22, %11
+  ret void
+}

llvm/test/Transforms/LICM/scalar-promote-memmodel.ll

 ; CHECK-NEXT:    [[INC2:%.*]] = phi i32 [ [[G_PROMOTED]], [[ENTRY:%.*]] ], [ [[INC1:%.*]], [[FOR_INC:%.*]] ]
 ; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC5:%.*]], [[FOR_INC]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_INC]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[INC2]], 1
-; CHECK-NEXT:    store i32 [[INC]], i32* @g, align 4
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INC1]] = phi i32 [ [[INC]], [[IF_THEN]] ], [ [[INC2]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[INC5]] = add nsw i32 [[I_0]], 1
 ; CHECK-NEXT:    br label [[FOR_COND]]
 ; CHECK:       for.end:
+; CHECK-NEXT:    [[INC2_LCSSA:%.*]] = phi i32 [ [[INC2]], [[FOR_COND]] ]
+; CHECK-NEXT:    store i32 [[INC2_LCSSA]], i32* @g, align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc5, %for.inc ]
   %cmp = icmp slt i32 %i.0, %n

llvm/test/Transforms/LICM/scalar-promote-opaque-ptrs.ll

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[X22:%.*]] = phi i32 [ [[LOCAL_PROMOTED]], [[ENTRY:%.*]] ], [ [[X21:%.*]], [[ELSE:%.*]] ]
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[NEXT:%.*]], [[ELSE]] ]
 ; CHECK-NEXT:    [[X2:%.*]] = call i32 @opaque(i32 [[X22]])
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[ELSE]]
 ; CHECK:       if:
-; CHECK-NEXT:    store i32 [[X2]], ptr [[LOCAL]], align 4
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[X21]] = phi i32 [ [[X2]], [[IF]] ], [ [[X22]], [[LOOP]] ]
 ; CHECK-NEXT:    [[NEXT]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[NEXT]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
+; CHECK-NEXT:    [[X21_LCSSA:%.*]] = phi i32 [ [[X21]], [[ELSE]] ]
+; CHECK-NEXT:    store i32 [[X21_LCSSA]], ptr [[LOCAL]], align 4
 ; CHECK-NEXT:    [[RET:%.*]] = load i32, ptr [[LOCAL]], align 4
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   %local = alloca i32
   call void @capture(i32* %local)
   br label %loop
 loop:

llvm/test/Transforms/LICM/scalar-promote.ll

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[X22:%.*]] = phi i32 [ [[LOCAL_PROMOTED]], [[ENTRY:%.*]] ], [ [[X21:%.*]], [[ELSE:%.*]] ]
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[NEXT:%.*]], [[ELSE]] ]
 ; CHECK-NEXT:    [[X2:%.*]] = call i32 @opaque(i32 [[X22]])
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[ELSE]]
 ; CHECK:       if:
-; CHECK-NEXT:    store i32 [[X2]], i32* [[LOCAL]], align 4
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[X21]] = phi i32 [ [[X2]], [[IF]] ], [ [[X22]], [[LOOP]] ]
 ; CHECK-NEXT:    [[NEXT]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[NEXT]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
+; CHECK-NEXT:    [[X21_LCSSA:%.*]] = phi i32 [ [[X21]], [[ELSE]] ]
+; CHECK-NEXT:    store i32 [[X21_LCSSA]], i32* [[LOCAL]], align 4
 ; CHECK-NEXT:    [[RET:%.*]] = load i32, i32* [[LOCAL]], align 4
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   %local = alloca i32
   call void @capture(i32* %local)
   br label %loop
 loop:

 ; CHECK-NEXT:    [[PTR_PROMOTED:%.*]] = load i8, i8* [[PTR:%.*]], align 1
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[INC1:%.*]] = phi i8 [ [[PTR_PROMOTED]], [[ENTRY:%.*]] ], [ [[INC1]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[I:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY]] ], [ [[ADD:%.*]], [[LOOP_LATCH]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[I]], 4
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 ; CHECK:       loop.latch:
-; CHECK-NEXT:    store i8 [[INC1]], i8* [[PTR]], align 1
 ; CHECK-NEXT:    [[ADD]] = add i8 [[I]], [[INC1]]
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 ; CHECK:       exit:
+; CHECK-NEXT:    [[INC1_LCSSA:%.*]] = phi i8 [ [[INC1]], [[LOOP_HEADER]] ]
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i8 [ [[I]], [[LOOP_HEADER]] ]
+; CHECK-NEXT:    store i8 [[INC1_LCSSA]], i8* [[PTR]], align 1
 ; CHECK-NEXT:    ret i8 [[I_LCSSA]]
 ;
 entry:
   br label %loop.header
 
 loop.header:
   %i = phi i8 [ %start, %entry ], [ %add, %loop.latch ]
   %cmp = icmp ult i8 %i, 4