Page MenuHomePhabricator

[Attributor] Pointer privatization attribute (argument promotion)
AcceptedPublic

Authored by jdoerfert on Oct 10 2019, 7:36 PM.

Details

Summary

A pointer is privatizeable if it can be replaced by a new, private one.
Privatizing pointer reduces the use count, interaction between unrelated
code parts. This is a first step towards replacing argument promotion.
While we can already handle recursion (unlike argument promotion!) we
are restricted to stack allocations for now because we do not analyze
the uses in the callee.

All argument promotion test now run the Attributor as well.

Diff Detail

Event Timeline

jdoerfert created this revision.Oct 10 2019, 7:36 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 10 2019, 7:36 PM

I went through all the tests, added mem2reg/sroa where approriate and modified the source sometimes, mostly to avoid UB. I think the results of the Attributor look good, all problems should have been addressed already.

lebedev.ri added inline comments.Oct 16 2019, 11:59 AM
llvm/test/Transforms/ArgumentPromotion/control-flow2.ll
27–31 ↗(On Diff #224526)

This is why i'm really pushing on using --check-prefixes=ALL,ARGPROMOTION from the getgo :[

35 ↗(On Diff #224526)

I strongly believe you want to precommit test changes+regeneration first.

jdoerfert marked 2 inline comments as done.
jdoerfert added inline comments.
llvm/test/Transforms/ArgumentPromotion/control-flow2.ll
27–31 ↗(On Diff #224526)

Agreed.

35 ↗(On Diff #224526)

I will update the test lines after the D68766 update. Do you want me to split test changes, e.g., that remove UB, as well?

Update the tests

jdoerfert updated this revision to Diff 227335.Oct 31 2019, 1:41 PM

Update tests

I'll copy the tests into the new Attributor test folder. Any other comments? @uenoku @sstefan1

uenoku added a comment.EditedDec 12 2019, 6:57 AM

Looks generally fine.
I couldn't imagine what is Pointer privatization at first hand. Could you add an example result of Pointer privatization? Like,

int f(int* ptr){
 ...
}
=>
int f(int p){
 int* ptr = &p;
 ...
}

And I guess the current implementation always does privatization if possible. I think the cost may increase in some cases, right? What do you think about?

llvm/include/llvm/Transforms/IPO/Attributor.h
2205

Could you add comments for the condition of whether the pointer can be replaced a private one?

2217

nit: choose

llvm/test/Transforms/ArgumentPromotion/chained.ll
18 ↗(On Diff #227335)

Please add FIXME here for AAValueSimplify.

Looks generally fine.
I couldn't imagine what is Pointer privatization at first hand. Could you add an example result of Pointer privatization? Like,

int f(int* ptr){
 ...
}
=>
int f(int p){
 int* ptr = &p;
 ...
}

I will add the example to the class comment in the header file.

For the record:
Privatization, at least the part implemented so far, is roughly argument promotion. Instead of passing a pointer, pass the values accessed through it by the callee.
The existing argument promotion does not do privatization but tries to replace the uses of the pointer with the values passed right away. Privatization is simpler in that
regard but later, partially because of this, also more powerful.

And I guess the current implementation always does privatization if possible. I think the cost may increase in some cases. What do you think about?

That is correct. So far, we build the Attribtor to be powerful (=applicable) not to be "smart" about costs. We'll have to write heurisitcs soon but before that I want to ask people to test the powerful version in order to get more coverage and sniff out bugs.

In fact, we might always do privatization once another piece of code I have only locally is available. With it, privatization might cause arbitrarily many arguments at the call site but we can always recover the original call site from it. More on that later though. For comparison: ArgumentPromotion restricts the size of the structs that are expanded arbitrarily to 3, which is beyond me.

uenoku accepted this revision.Dec 13 2019, 3:46 AM

LGTM from my side but please make sure that it passes test-suite.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
846

I think you can put this function to llvm namespace and split commit.

This revision is now accepted and ready to land.Dec 13 2019, 3:46 AM

LGTM from my side but please make sure that it passes test-suite.

Will do.

I have to wait for D68765 first but not necessarily for the update scrip patches (they are blocked by the update test infrastructure patch).

jdoerfert marked 5 inline comments as done.

Addressed comments

jdoerfert added inline comments.Dec 14 2019, 12:24 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
2205

Done.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
846

I would like to get rid of this, the Attributor should directly use a more specialized form of areFunctionArgsABICompatible. I'll add a TODO.

efriedma added inline comments.Dec 16 2019, 6:38 PM
llvm/lib/Transforms/IPO/Attributor.cpp
4697

No alignment set on loads?

4732

No alignment set on alloca?

4796

isArrayAllocation()

jdoerfert marked 2 inline comments as done.Dec 16 2019, 7:01 PM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4697

I'll add the alignment for the alloca below based on the alignment of the pointer it replaces. The loads and stores will be annotated by the next run of the Attributor automatically.

We can also consider not emitting it if we can prove it is not needed, though that will not always be the case and it will require an analysis we do not yet have (something like AAAccessTracker).

Finally, SROA should, in the good case, eliminate the alloca completely.

4796

Will do.

efriedma added inline comments.Dec 17 2019, 8:58 AM
llvm/lib/Transforms/IPO/Attributor.cpp
4697

The loads and stores will be annotated by the next run of the Attributor automatically.

The default alignment of a load is the alignment of the load's type, as computed by the datalayout. This might be too high, depending on the pointer.

jdoerfert marked an inline comment as done.Dec 17 2019, 9:21 AM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4697

The default alignment of a load is the alignment of the load's type, as computed by the datalayout.

Sure.

This might be too high, depending on the pointer.

How could that be? We create the pointer with a proper type (the alloca) below. Shouldn't the alloca take the default alignment into account when the memory is allocated?

efriedma added inline comments.Dec 17 2019, 10:12 AM
llvm/lib/Transforms/IPO/Attributor.cpp
4697

If you create an alloca, then load/store to that pointer, the default alignments will work, yes. But that isn't what's happening here, is it? The alloca is in the callee, and this load is in the caller.

jdoerfert marked an inline comment as done.Dec 17 2019, 11:57 AM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4697

With this patch we always have an alloca or an argument with some pointer to (struct) type which we only access through proper gep addressing. I don't think this can create an alignment issue.

I get that the alloca needs to be aligned with a higher value if the pointer was marked as such, but I already said that will be fixed.

efriedma added inline comments.Dec 17 2019, 12:42 PM
llvm/lib/Transforms/IPO/Attributor.cpp
4697

Pointers can be misaligned, generally. For example:

define void @f() {
entry:
  %a = alloca i32, align 1
  call void @g(i32* %a)
  ret void
}

define internal void @g(i32* %a) {
  %aa = load i32, i32* %a, align 1
  call void @z(aa)
}

declare void @z(i32)

As far as I can tell, your patch will introduce a misaligned load into @f().

(C generally provides additional guarantees based on the pointee type of a pointer, but there isn't any corresponding rule for IR pointers.)

jdoerfert marked an inline comment as done.Dec 17 2019, 3:25 PM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4697

I finally understand your concern, sorry that it took so long.

I played around a bit to see what we currently do and I found this interesting: https://godbolt.org/z/2q_oqH
We basically align the alloca naturally at some point.

I would for now just set the alignment to 1 and add a TODO. For these loads, the Attributor can find a better alignment in the next run anyway and this allows me to not amend this patch too much. The TODO will explain the situation and we can work on a better solution from then. Maybe, if it is very simple, I'll directly use the AAAlign logic to get a lower bound instead. Long story short, I'll make sure these loads are properly aligned and we test for this.