Page MenuHomePhabricator

[OpaquePtr] Support forward references in textual IR
ClosedPublic

Authored by nikic on Jun 25 2021, 1:59 PM.

Details

Summary

Currently, LLParser will create a Function/GlobalVariable forward reference based on the desired pointer type and then modify it when it is declared. With opaque pointers, we generally do not know the correct type to use until we see the declaration.

Solve this by creating the forward reference with a dummy type, and then performing a RAUW with the correct Function/GlobalVariable when it is declared. The approach is shamelessly stolen from https://github.com/TNorthover/llvm-project/commit/b5b55963f62038319fa7a8b1b232226ba1d8ef3c.

This results in a change to the use list order, which is why we see test changes on some module passes that are not stable under reordering.

Diff Detail

Event Timeline

nikic created this revision.Jun 25 2021, 1:59 PM
nikic requested review of this revision.Jun 25 2021, 1:59 PM
Herald added a reviewer: sstefan1. · View Herald Transcript
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
nikic added a comment.Jun 25 2021, 3:24 PM

llvm/test/Assembler/metadata-use-uselistorder.ll is failing on Windows, but not locally :(

Out of curiosity, I ran find . -name '*.ll' -exec echo '{}' \; -exec build/bin/verify-uselistorder {} \; >out 2>&1 without this patch, and hit quite a few failures :/

llvm/test/Assembler/metadata-use-uselistorder.ll is failing on Windows, but not locally :(

Likely indicates non-determinism in the use-list order, which seems worth fixing (or non-determinism in the prediction; that surface area is much smaller, but maybe not well-enough tested). I'm staring at your change trying to figure out what that could be and I'm not seeing anything though...

Out of curiosity, I ran find . -name '*.ll' -exec echo '{}' \; -exec build/bin/verify-uselistorder {} \; >out 2>&1 without this patch, and hit quite a few failures :/

IIRC, that passed when verify-uselistorder originally landed... a shame it's getting in the way so much for the opaque pointer stuff.

dexonsmith added inline comments.Jun 25 2021, 4:01 PM
llvm/lib/AsmParser/LLParser.cpp
1155–1156

Seems like we could probably keep this behaviour somehow -- getting the global to the "correct" spot in the module might avoid some of the testcase churn as well. See the example I call out below.

llvm/test/Transforms/LowerTypeTests/icall-branch-funnel.ll
9–10

I'm wondering if churn like this can be avoided by keeping some logic to move things back to the "correct" spot.

dexonsmith added inline comments.Jun 25 2021, 4:06 PM
llvm/lib/AsmParser/LLParser.cpp
1155–1156

Ah, except, I see, reading more carefully: the newly created global variable is already in the "correct" spot. In which case the churn is likely caused by the use-list order difference...

llvm/test/Assembler/metadata-use-uselistorder.ll is failing on Windows, but not locally :(

If you can get access to a Windows machine, are you able to post the output of this somewhere?

% verify-uselistorder llvm/test/Assembler/metadata-use-uselistorder.ll -debug-only uselistorder

Out of curiosity, I ran find . -name '*.ll' -exec echo '{}' \; -exec build/bin/verify-uselistorder {} \; >out 2>&1 without this patch, and hit quite a few failures :/

Not sure how many failures you're seeing. I saw 132 when I ran it. https://reviews.llvm.org/D104959 brings that down to 60. Looking at the rest.

Out of curiosity, I ran find . -name '*.ll' -exec echo '{}' \; -exec build/bin/verify-uselistorder {} \; >out 2>&1 without this patch, and hit quite a few failures :/

Not sure how many failures you're seeing. I saw 132 when I ran it. https://reviews.llvm.org/D104959 brings that down to 60. Looking at the rest.

I looked at llvm/test/Transforms/CallSiteSplitting/lpad.ll. This fails because the implicit i1* null hung-off operands of the function don't get ordered properly. Here is a minimal repro:

@personality = external global i8
define void @f1(i1* %param) personality i8* @personality {
entry:
  %cmp = icmp eq i1* %param, null
  unreachable
}

The prefix-data and prologue-data fields are (implicitly) uses of i1* null because there's a personality. I'm having trouble reasoning about exactly how to fix this one since the bitcode reader handles these strangely... but I hacked verify-uselistorder to ignore mismatches for all ConstantData values, and that hides this and gets the failure list from 60 down to 35. (Really, no one should ever walk the use-list of ConstantData; it'd be worth guaranteeing that at some point, and then we could skip computing/storing use-list ordering for them...) I can probably whittle this down next week if it's blocking you.

Still curious to hear what the windows failure is.

nikic added a comment.Jun 26 2021, 1:33 AM

llvm/test/Assembler/metadata-use-uselistorder.ll is failing on Windows, but not locally :(

If you can get access to a Windows machine, are you able to post the output of this somewhere?

I don't have access to Windows, but I figured out what the platform dependent part here is: verify-uselistorder performs shuffles of the use list, and these are based on the std rng infrastructure, so it's prone to be platform dependent. Running the test with --num-shuffles 2 makes it reproduce on Linux.

In the end, it's very simple to reproduce, we just need three calls to a forward declaration:

define void @test() {
  call void @dummy(i32 0)
  call void @dummy(i32 1)
  call void @dummy(i32 2)
  ret void
}         
  
declare void @dummy(i32)

And then we get this use-list order mismatch: https://gist.github.com/nikic/dfa27b1620b9501baf6fc70f87ca6fb2

nikic added a comment.Jun 26 2021, 1:59 AM

My suspicion here is that this happens whenever an explicit uselistorder for the forward declaration is present inside a function. In that case we'll perform the use list order sort on the forward declaration, and rauw it later, breaking the order. Though I don't really understand how per-function uselistorder for global symbols is even supposed to work -- shouldn't this uselistorder be at the module level?

I figured out what the platform dependent part here is: verify-uselistorder performs shuffles of the use list, and these are based on the std rng infrastructure, so it's prone to be platform dependent. Running the test with --num-shuffles 2 makes it reproduce on Linux.

Ah, of course. Maybe the default for --num-shuffles should be increased?

My suspicion here is that this happens whenever an explicit uselistorder for the forward declaration is present inside a function. In that case we'll perform the use list order sort on the forward declaration, and rauw it later, breaking the order.

Note that the RAUW will reverse the order at a predictable time, so this is possible to model. But your approach in https://reviews.llvm.org/D104976 seems simpler.

aeubanks added inline comments.
llvm/lib/AsmParser/LLParser.cpp
1466

With --force-opaque-pointers, we never get to Function::Create(). Can we always create a GlobalVariable (or always create a Function) and RAUW with the proper GlobalVariable/Function later?

llvm/lib/IR/AsmWriter.cpp
188–191

could you explain this change?

dexonsmith added inline comments.Jun 28 2021, 3:42 PM
llvm/lib/IR/AsmWriter.cpp
188–191

I can at least explain what GetsReversed means (maybe this should have a better comment / name?). This flag indicates that the use-list gets reversed when value is defined. This should be true if the reader will call RAUW on a forward-declared value, false if the value itself is created on first use and modified in place (or not at all) when it's defined.

nikic updated this revision to Diff 355274.Jun 29 2021, 9:33 AM

Add comment, handle opaque pointer case more explicitly.

aeubanks accepted this revision.Jun 29 2021, 9:41 AM

lgtm, thanks!

llvm/lib/AsmParser/LLParser.cpp
1466

now we could always use a GlobalVariable even without opaque pointers right?
probably doesn't really matter

This revision is now accepted and ready to land.Jun 29 2021, 9:41 AM
nikic added inline comments.Jun 29 2021, 9:49 AM
llvm/lib/AsmParser/LLParser.cpp
1466

It's not possible to create a GlobalVariable of function type, so we do need to distinguish the cases. For non-opaque pointers matching the type is important, because using a different type would requite a pointer bitcast. For opaque pointers, this doesn't matter.

This revision was automatically updated to reflect the committed changes.