This is an archive of the discontinued LLVM Phabricator instance.

[SROA] For non-speculatable `load`s of `select`s -- split block, insert then/else blocks, form two-entry PHI node
ClosedPublic

Authored by lebedev.ri on Nov 17 2022, 2:29 PM.

Details

Summary

Currently, SROA is CFG-preserving.
Not doing so does not affect any pipeline test. (???)
Internally, SROA requires Dominator Tree, and uses it solely for the final -mem2reg call.

By design, we can't really SROA alloca if their address escapes somehow,
but we have logic to deal with load of select/PHI,
where at least one of the possible addresses prevents promotion,
by speculating the loads and selecting between loaded values.

As one would expect, that requires ensuring that the speculation is actually legal.
Even ignoring complexity bailouts, that logic does not deal with everything,
e.g. isSafeToLoadUnconditionally() does not recurse into hands of select.
There can also be cases where the load is genuinely non-speculate.

So if we can't prove that the load can be speculated,
unfold the select, produce two-entry phi node, and perform predicated load.

Now, that transformation must obviously update Dominator Tree,
since we require it later on. Doing so is trivial.
Additionally, we don't want to do this for the final SROA invocation (D136806).

In the end, this ends up having negative (!) compile-time cost:
https://llvm-compile-time-tracker.com/compare.php?from=c6d7e80ec4c17a415673b1cfd25924f98ac83608&to=ddf9600365093ea50d7e278696cbfa01641c959d&stat=instructions:u

Though indeed, this only deals with selects, PHIs are still using speculation.

Should we update some more analysis?

Diff Detail

Event Timeline

lebedev.ri created this revision.Nov 17 2022, 2:29 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 17 2022, 2:29 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
lebedev.ri requested review of this revision.Nov 17 2022, 2:29 PM
arsenm added inline comments.Nov 18 2022, 2:09 PM
llvm/include/llvm/Transforms/Scalar/SROA.h
106–109

Are there any cases where this should still try to speculate?

llvm/lib/Transforms/Scalar/SROA.cpp
1417

Single quote newline

lebedev.ri added inline comments.Nov 18 2022, 2:11 PM
llvm/include/llvm/Transforms/Scalar/SROA.h
106–109

I'm not sure i understand the question.
As it can be seen from the rest of the diff here,
for select's, we will always form diamond control flow and two-entry phi node,
and never check if we can speculate load.
For PHI's, we still speculate.

lebedev.ri added inline comments.Nov 18 2022, 2:19 PM
llvm/include/llvm/Transforms/Scalar/SROA.h
106–109

One improvement over this we can do, is to cache
all of the pointers derived from the current alloca,
and speculate the loads that belong to that set.
That might be cheap to do. Is that what you had in mind?

We also should probably report CFG as preserved unless we actually changed it.

lebedev.ri planned changes to this revision.Nov 18 2022, 4:53 PM

I'm guessing we should keep the old approach at least for the new last SROA run.
Not quite sure about PHI handling yet.

lebedev.ri retitled this revision from [SROA] Change how we speculate `load`s of `select`s -- split block, insert then/else blocks, form two-entry PHI node to [SROA] For non-speculatable `load`s of `select`s -- split block, insert then/else blocks, form two-entry PHI node.
lebedev.ri edited the summary of this revision. (Show Details)

Okay, only modifying CFG if we must is even better.
Please take a look :)

arsenm added inline comments.Nov 30 2022, 6:44 PM
llvm/include/llvm/Transforms/Scalar/SROA.h
92

Move to last field?

llvm/lib/Passes/PassBuilder.cpp
840

I thought pass options were-spelled-like-this?

llvm/lib/Transforms/Scalar/SROA.cpp
1417–1418

I know it was already like this, but can't you just do CreateAlignedLoad to start?

1487

Missing check if CFG modify is allowed? Could also move this out to where this is called and check the return value (which it looks like is already there)

4961–4963

Why not just OS << (PreserveCFG ? "<PreserveCFG>" : "<ModifyCFG>";

llvm/test/Transforms/SROA/2009-02-20-InstCombine-SROA.ll
274–276

Just remove the prefixes?

lebedev.ri marked 8 inline comments as done.

@arsenm thank you for taking a look!
I believe, this addresses your comments.

llvm/include/llvm/Transforms/Scalar/SROA.h
92

I'm guessing you meant "to the end of this var decl group?"

llvm/lib/Passes/PassBuilder.cpp
840

Meh. Okay.

llvm/lib/Transforms/Scalar/SROA.cpp
1487

No, nothing is missing, this is just defensive coding.

If we can't modify cfg, then we really won't get here,
and this just confirms that invariant.

E.g. we won't pass DTU into call to rewriteSelectInstLoads()
if we are not allowed to perform CFG changes.

And earlier, see if (PreserveCFG) return {}; bailouts in isSafeSelectToSpeculate().

llvm/test/Transforms/SROA/2009-02-20-InstCombine-SROA.ll
274–276

Unless you really insist, i'd like to keep this as is.
If i remove the prefixes,

  1. the tests become unconsistent. because currently they all have the same run lines and check prefixes
  2. Should the run lines start producing different outputs, without this, the output will get silently lost, and requires manual changes to unbreak

The latter is really painful in e.g. codegen tests.
I would really really prefer to avoid creating that problem.

lebedev.ri updated this revision to Diff 479727.Dec 2 2022, 1:17 PM

Add a few more tests (non-simple loads, select-of-select).
mem2reg bails on volatile (but not atomic!) loads,
so we shouldn't form predicated loads for them.

arsenm added inline comments.Dec 5 2022, 11:27 AM
llvm/include/llvm/Transforms/Scalar/SROA.h
140

Use opaque pointer example?

llvm/lib/Passes/PassRegistry.def
481

outdated option names?

lebedev.ri marked 2 inline comments as done.

@arsenm thank you for taking a look!
Addressing comments.

arsenm accepted this revision.Dec 7 2022, 5:46 PM
This revision is now accepted and ready to land.Dec 7 2022, 5:46 PM
nikic added inline comments.Dec 8 2022, 12:08 AM
llvm/include/llvm/Transforms/Scalar/SROA.h
24

nit: Wrong include style

llvm/lib/Passes/PassBuilder.cpp
849

Do I understand correctly that this will prevent doing a plain -passes=sroa run? If so, please pick one of these as a default -- I don't really care which one, but people who just want to clean up some IR with SROA certainly don't need to know about these details. This would also violate existing practice for all other passes.

lebedev.ri updated this revision to Diff 481258.Dec 8 2022, 5:49 AM
lebedev.ri marked 2 inline comments as done.

@arsenm @nikic thank you for the review!

This revision was landed with ongoing or failed builds.Dec 8 2022, 5:52 AM
This revision was automatically updated to reflect the committed changes.

Hello,

I noticed that when compiling with gcc I get the following new warning with this patch:

00:14:51 ../include/llvm/Transforms/Scalar/SROA.h:95:7: warning: 'llvm::SROAPass' declared with greater visibility than the type of its field 'llvm::SROAPass::SelectsToRewrite' [-Wattributes]
00:14:51    95 | class SROAPass : public PassInfoMixin<SROAPass> {
00:14:51       |       ^~~~~~~~

I guess it's because

using PossiblySpeculatableLoad =
    PointerIntPair<LoadInst *, 2, sroa::SelectHandSpeculativity>;
using PossiblySpeculatableLoads = SmallVector<PossiblySpeculatableLoad, 2>;

are declared inside

namespace sroa LLVM_LIBRARY_VISIBILITY {

but then PossiblySpeculatableLoads is used in the SROAPass member

SmallMapVector<SelectInst *, sroa::PossiblySpeculatableLoads, 8>
    SelectsToRewrite;

I've no idea if this is anythinig to care about though?

Hello,

I noticed that when compiling with gcc I get the following new warning with this patch:

00:14:51 ../include/llvm/Transforms/Scalar/SROA.h:95:7: warning: 'llvm::SROAPass' declared with greater visibility than the type of its field 'llvm::SROAPass::SelectsToRewrite' [-Wattributes]
00:14:51    95 | class SROAPass : public PassInfoMixin<SROAPass> {
00:14:51       |       ^~~~~~~~

I guess it's because

using PossiblySpeculatableLoad =
    PointerIntPair<LoadInst *, 2, sroa::SelectHandSpeculativity>;
using PossiblySpeculatableLoads = SmallVector<PossiblySpeculatableLoad, 2>;

are declared inside

namespace sroa LLVM_LIBRARY_VISIBILITY {

but then PossiblySpeculatableLoads is used in the SROAPass member

SmallMapVector<SelectInst *, sroa::PossiblySpeculatableLoads, 8>
    SelectsToRewrite;

I've no idea if this is anythinig to care about though?

Yeah, @arsenm told me about that. I'm not sure about this diagnostic.
What really worries me though, is that we don't appear to have GCC -Werror bots?

Hello,

I noticed that when compiling with gcc I get the following new warning with this patch:

00:14:51 ../include/llvm/Transforms/Scalar/SROA.h:95:7: warning: 'llvm::SROAPass' declared with greater visibility than the type of its field 'llvm::SROAPass::SelectsToRewrite' [-Wattributes]
00:14:51    95 | class SROAPass : public PassInfoMixin<SROAPass> {
00:14:51       |       ^~~~~~~~

I guess it's because

using PossiblySpeculatableLoad =
    PointerIntPair<LoadInst *, 2, sroa::SelectHandSpeculativity>;
using PossiblySpeculatableLoads = SmallVector<PossiblySpeculatableLoad, 2>;

are declared inside

namespace sroa LLVM_LIBRARY_VISIBILITY {

but then PossiblySpeculatableLoads is used in the SROAPass member

SmallMapVector<SelectInst *, sroa::PossiblySpeculatableLoads, 8>
    SelectsToRewrite;

I've no idea if this is anythinig to care about though?

Yeah, @arsenm told me about that. I'm not sure about this diagnostic.
What really worries me though, is that we don't appear to have GCC -Werror bots?

Yeah, llvm isn't clean of gcc warnings.
We compile with gcc downstream and used -Werror at first but had to give up that since there are no public bots running with it.
Now we just notice when new warnings pop up instead.

mkitzan added inline comments.
llvm/lib/Transforms/Scalar/SROA.cpp
1409

Our out-of-tree backend is asserting in this function call (particularly at assert(cast<PointerType>(Ptr->getType())->isOpaqueOrPointeeTypeMatches(Ty)) which occurs while creating the load). I suspect this is due to the lost bitcasts, since when I add them back there's no assert.

The code I have adding the bitcasts back looks like the following:

IRB.SetInsertPoint(&LI);

// OUT OF TREE
if (SI.hasOneUse()) {
  if (BitCastInst *BC = dyn_cast<BitCastInst>(SI.user_back())) {
    // assert(BC->user_back() == &LI); <- unclear if this is guaranteed
    TV = IRB.CreateBitCast(TV, BC->getType(), TV->getName() + ".sroa.cast");
    FV = IRB.CreateBitCast(FV, BC->getType(), FV->getName() + ".sroa.cast");
  }
}
// END OUT OF TREE

LoadInst *TL = ...

To be honest, I have not entirely analyzed this patch, so I'm not confident that the way I have added the bitcasts back is legal (especially now that there's no while loop on SI's uses...). Could you advise if this is legal/correct (to unblock us)? I can try to get an anonymized test case for this, so a full fix can be made.

lebedev.ri added inline comments.Dec 20 2022, 5:48 PM
llvm/lib/Transforms/Scalar/SROA.cpp
1409

We are literally days away from stopping accepting such fixes.
That being said, let me fix this one...

lebedev.ri marked an inline comment as done.Dec 20 2022, 6:18 PM
lebedev.ri added inline comments.
llvm/lib/Transforms/Scalar/SROA.cpp
1409

9f27f4536e19e93349b0662338408efe6d1cb2fd, but it is probably one of last ones of it's kind.

mkitzan added inline comments.Dec 21 2022, 9:14 AM
llvm/lib/Transforms/Scalar/SROA.cpp
1409

Thanks for the quick turn around

lebedev.ri marked 2 inline comments as not done.Dec 21 2022, 9:22 AM
lebedev.ri added inline comments.
llvm/lib/Transforms/Scalar/SROA.cpp
1409

Sorry, that was too quick and it got reverted.

@nikic please can you estimate when we switch to not dealing with typed pointer bugs?

nikic added inline comments.Dec 21 2022, 10:36 AM
llvm/lib/Transforms/Scalar/SROA.cpp
1409

Here's my proposal for a hard timeline: https://reviews.llvm.org/D140487 (tl;dr supported until release/16.x branch creation on Jan 24th).

lebedev.ri marked 3 inline comments as done.Dec 21 2022, 2:53 PM
lebedev.ri added inline comments.
llvm/lib/Transforms/Scalar/SROA.cpp
1409

2cb393590ea537b06fa66e6d847a1159c227a313, looks like it stuck this time around.

mkitzan added inline comments.Dec 21 2022, 4:20 PM
llvm/lib/Transforms/Scalar/SROA.cpp
1409

Haha no worries. Glad it's finally landed 👍

Hi,

Hello,

I noticed that when compiling with gcc I get the following new warning with this patch:

00:14:51 ../include/llvm/Transforms/Scalar/SROA.h:95:7: warning: 'llvm::SROAPass' declared with greater visibility than the type of its field 'llvm::SROAPass::SelectsToRewrite' [-Wattributes]
00:14:51    95 | class SROAPass : public PassInfoMixin<SROAPass> {
00:14:51       |       ^~~~~~~~

I guess it's because

using PossiblySpeculatableLoad =
    PointerIntPair<LoadInst *, 2, sroa::SelectHandSpeculativity>;
using PossiblySpeculatableLoads = SmallVector<PossiblySpeculatableLoad, 2>;

are declared inside

namespace sroa LLVM_LIBRARY_VISIBILITY {

but then PossiblySpeculatableLoads is used in the SROAPass member

SmallMapVector<SelectInst *, sroa::PossiblySpeculatableLoads, 8>
    SelectsToRewrite;

I've no idea if this is anythinig to care about though?

Yeah, @arsenm told me about that. I'm not sure about this diagnostic.
What really worries me though, is that we don't appear to have GCC -Werror bots?

This warning is still present in current builds using GCC, also using recent GCC versions, see this buildbot:

/home/buildbot/as-builder-4/llvm-clang-x86_64-expensive-checks-ubuntu/llvm-project/llvm/include/llvm/Transforms/Scalar/SROA.h:96:7: warning: ‘llvm::SROAPass’ declared with greater visibility than the type of its field ‘llvm::SROAPass::SelectsToRewrite’ [-Wattributes]

The warning does seem to point at a genuine problem. The intent of the sroa namespace is to hide details from clients (possibly in other modules), see here.

/// A private "module" namespace for types and utilities used by SROA. These
/// are implementation details and should not be used by clients.
namespace LLVM_LIBRARY_VISIBILITY sroa {

But because the SROAPass has the field SelectsToRewrite, which contains sroa::PossiblySpeculatableLoads values, it is required to know these details to calculate its size, determine its layout, etc.

Would it be an option to put PossiblySpeculatableLoads (and its constituents) in another namespace (for example sroa_detail), with normal visibility? Or can we store the SelectsToRewrite as a unique_ptr rather than as the map vector directly (pimpl pattern)? The latter would allow to remove the details of PossiblySpeculatableLoads (and its constituents) from the SROA.h header, but would require to follow an extra indirection to access SelectsToRewrite.

Thanks!

nikic added a comment.Nov 13 2023, 2:11 AM

@brunodf Ideally, we'd move the SROA implementation into a separate class in the cpp file and only export a thin NewPM wrapper around it in the header.

@brunodf Ideally, we'd move the SROA implementation into a separate class in the cpp file and only export a thin NewPM wrapper around it in the header.

This is a pull request implementing the reorganization suggested by @nikic : https://github.com/llvm/llvm-project/pull/72846
It solves the GCC warning obviously, but it is also a better organization, it can do away with the llvm::sroa namespace entirely, etc.
If you can, please review it.